Hostname: page-component-586b7cd67f-tf8b9 Total loading time: 0 Render date: 2024-11-28T15:21:35.708Z Has data issue: false hasContentIssue false
  • English
  • Français

BigYAP: Exo-compilation meets UDI

Published online by Cambridge University Press:  25 September 2013

VÍTOR SANTOS COSTA  and
DAVID VAZ
VÍTOR SANTOS COSTA
Affiliation:
CRACS - DCC/FCUP, University of Porto, Portugal
DAVID VAZ
Affiliation:
CRACS - DCC/FCUP, University of Porto, Portugal
Get access Rights & Permissions [Opens in a new window]

Abstract

The widespread availability of large data-sets poses both an opportunity and a challenge to logic programming. A first approach is to couple a relational database with logic programming, say, a Prolog system with MySQL. While this approach does pay off in cases where the data cannot reside in main memory, it is known to introduce substantial overheads. Ideally, we would like the Prolog system to deal with large data-sets in an efficient way both in terms of memory and of processing time. Just In Time Indexing (JITI) was mainly motivated by this challenge, and can work quite well in many application.

Exo-compilation, designed to deal with large tables, is a next step that achieves very interesting results, reducing the memory footprint over two thirds. We show that combining exo-compilation with Just In Time Indexing can have significant advantages both in terms of memory usage and in terms of execution time.

An alternative path that is relevant for many applications is User-Defined Indexing (UDI). This allows the use of specialized indexing for specific applications, say the spatial indexing crucial to any spatial system. The UDI sees indexing as pluggable modules, and can naturally be combined with Exo-compilation. We do so by using UDI with exo-data, and incorporating ideas from the UDI into high-performance indexers for specific tasks.

Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 13 , Special Issue 4-5: 29th International Conference on Logic Programming , July 2013 , pp. 799 - 813
Copyright
Copyright © 2013 [VÍTOR SANTOS COSTA and DAVID VAZ] 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Angelopoulos, N., Santos Costa, V., ao Azevedo, J., Wielemaker, J., Camacho, R. and Wessels, L. 2013. Integrative functional statistics in logic programming. In Proc. of Practical Aspects of Declarative Languages, LNCS, vol. 7752, Rome, Italy. Accepted.Google Scholar
Ashburner, M., Ball, C. A., Blake, J. A., Botstein, D., Butler, H., Cherry, J. M., Davis, A. P., Dolinski, K., Dwight, S. S., Eppig, J. T., Harris, M. A., Hill, D. P., Issel-Tarver, L., Kasarskis, A., Lewis, S., Matese, J. C., Richardson, J. E., Ringwald, M., Rubin, G. M. and Sherlock, G. 2000. Gene ontology: Tool for the unification of biology. The Gene Ontology Consortium. Nature genetics 25, 1 (May), 25–29.CrossRefGoogle ScholarPubMed
Codd, E. F. 1970. A relational model for large shared data banks. Communications of the ACM 13, 6, 377–387.CrossRefGoogle Scholar
Conway, T., Henderson, F. and Somogyi, Z. 1995. Code Generation for Mercury. In Proceedings of the International Symposium on Logic Programming, Lloyd, J., Ed. MIT Press, Cambridge, 242–256.Google Scholar
Demoen, B., Mariën, A. and Callebaut, A. 1989. Indexing in Prolog. In Proceedings of the North American Conference on Logic Programming, Lusk, E. L. and Overbeek, R. A., Eds. Cleveland, Ohio, USA, 1001–1012.Google Scholar
Demoen, B. and Nguyen, P.-L. 2000. So many WAM variations, so little time. In LNAI 1861, Proceedings Computational Logic - CL 2000. Springer-Verlag, 1240–1254.Google Scholar
Demoen, B., Nguyen, P.-L., Santos Costa, V. and Somogyi, Z. 2007. Dealing with large predicates: Exo-compilation in the WAM and in Mercury. In Proceedings of the Seventh Colloquium on the Implementation of Constraint and Logic Programming (CICLOPS 2007), Abreu, S. and Costa, V. Santos, Eds. Porto, Portugal, 117–131.Google Scholar
Guo, H.-F. and Gupta, G. 2008. Simplifying dynamic programming via mode-directed tabling. Software: Practice and Experience 38, 1, 75–94.Google Scholar
Henke, C., Schmoll, C. and Zseby, T. 2007. Empirical Evaluation of Hash Functions for Multipoint Measurements. Tech. rep., Fraunhofer Institute FOKUS. 11.Google Scholar
Murray, R. E., Ryan, P. B. and Reisinger, S. J. 2012. Design and validation of a data simulation model for longitudinal healthcare data. In Proc. of the ANIA Annual Symposium, Vol. 1176–1185, Washington DC, USA.Google Scholar
Page, D., Santos Costa, V., Natarajan, S., Peissig, P., Barnard, A. and Caldwell, M. 2012. Identifying adverse drug events from multi-relational healthcare data. In Proceedings of the Twenty-Sixth Conference on Artificial Intelligence, AAAI-12, Hoffmann, J. and Selman, B., Eds.Google Scholar
Santos Costa, V. 2007. Prolog performance on larger datasets. In Practical Aspects of Declarative Languages, 9th International Symposium, PADL 2007, Nice, France, January 14–15, 2007., Hanus, M., Ed. Lecture Notes in Computer Science, vol. 4354, Springer, 185–199.Google Scholar
Santos Costa, V., Damas, L. and Rocha, R. 2012. The YAP Prolog system. Theory and Practice of Logic Programming 12, Special Issue 1–2, 5–34.CrossRefGoogle Scholar
Santos Costa, V., Sagonas, K. and Lopes, R. 2007. Demand-driven indexing of Prolog clauses. In Proceedings of the 23rd International Conference on Logic Programming, Dahl, V. and Niemelä, I., Eds. Lecture Notes in Computer Science, vol. 4670. Springer, 305–409.Google Scholar
Swift, T. and Warren, D. S. 2012. XSB: Extending Prolog with tabled logic programming. TPLP 12, 1–2, 157–187.Google Scholar
Van Roy, P. 1994. 1983–1993: The wonder years of sequential Prolog implementation. Journal of Logic Programming 19/20.Google Scholar
Vaz, D., Santos Costa, V. and Ferreira, M. 2009. User defined indexing. In Logic Programming, 25th International Conference, ICLP 2009, Pasadena, CA, USA, July 14–17, 2009. Proceedings, Hill, P. M. and Warren, D. S., Eds. Lecture Notes in Computer Science, vol. 5649, Springer, 372–386.Google Scholar
Warren, D. H. D. 1977. Implementing Prolog - Compiling Predicate Logic Programs. Tech. Rep. 39 and 40, Department of Artificial Intelligence, University of Edinburgh.Google Scholar
Warren, D. H. D. 1983. An Abstract Prolog Instruction Set. Technical Note 309, SRI International.Google Scholar
Wielemaker, J., Schrijvers, T., Triska, M. and Lager, T. 2012. SWI-Prolog. TPLP 12, 1–2, 67–96.Google Scholar
Zhou, N.-F. and Have, C. T. 2012. Efficient tabling of structured data with enhanced hash-consing. TPLP 12, 4–5, 547–563.Google Scholar