ABSTRACT Background Managing huge amount of data can benefit from the use of compact data structures (like the k 2 ‐tree) that store the information in compressed form (usually in main memory), and can manipulate it without having to decompress it. However, as the amount of data is continuously increasing, it will be common that the compact data structures do not entirely fit into main memory, thus they will have to use disk. Aims To provide an implementation of the k 2 ‐tree on external memory (disk). It will be a first approach that may serve as a baseline for future work. Materials and Methods The data structure was implemented. A formal evaluation of the time complexity of the main operations was given, as well as an extensive experimental evaluation, comparing it to a Linear Quat Tree on disk. Results The k 2 ‐tree was competitive of clearly surpassed the other structure in almost all cases. The memory footprint was always much lower. Discussion The experiments compared the behavior of the k 2 ‐tree with the Linear Quadtree, showing the k2‐tree as a better approach in general, in terms of efficiency and memory use. Conclusion The proposed implementation was successful, and it will serve as a baseline for future implementation of compact data structures on disk (either different implementation of the k 2 ‐tree, or different data structures).

Distance-based Join Queries (DJQs) have multiple applications in spatial databases, Geographic Information Systems, and other areas. The K Closest Pairs Query (KCPQ) and the ε Distance Join Query (εDJQ) are well-known DJQs that have been widely studied and can be solved using plane-sweep techniques, which are efficient but must keep the whole datasets in main memory. In this work, we propose DJQ algorithms that work with data represented using a k2-tree, a compact data structure for binary grids. Our algorithms solve KCPQ and εDJQ queries, as well as several window-constrained variants, taking advantage of the indexing capabilities of k2-trees to efficiently answer queries without the need to decompress the data. Our experimental evaluation with large datasets shows that k2-tree algorithms are up to 5 times faster than plane-sweep algorithms in KCPQ, and 5–30 times faster in εDJQ. In variants that are window-constrained, our algorithms are competitive in most scenarios and faster for large windows. Additionally, our algorithms are not very affected by the distribution of the data and yield much more predictable query times, showing up to 30 times smaller variance in query times than plane sweep, depending on the location of the query window.

k2-trees have been proved successful to represent in avery compact way different kinds of binary relations, such as web graphs, RDFs or raster data. In order to be a fully functional succinct representation for these domains, the k2-tree must support all the required operations for binary relations. In their original description, the authors include how to answer some of the most relevant queries over the k2-tree. In this paper, we extend this functionality and detail the algorithms to efficiently compute the k2-tree resulting from the union, intersection, difference or complement of binary relations represented using k2-trees.

Antique documents, which undoubtedly represent our cultural heritage and can be considered a very rich source of information, are kept in many countries only on libraries with historical archives. The antiquity and fragility of such documents makes their access very restricted. Considering that nowadays the Internet is one of the most interesting places to publish any kind of information, it seems logical to use it to both preserve our cultural heritage and provide a broader access to these documents. This work presents a virtual library that stores data, transcribed texts and digitalized pages of historic Spanish documents from the 16th–18th centuries. This virtual library has two main objectives: first, by offering a set of services, including a powerful user interface to search and browse the documents, a bulletin board, a chat, or mail boxes, the virtual library is transformed into a meeting place for researchers that use emblem books as sources of information for their studies. Second, the virtual library contributes to the preservation of emblem books. We shall describe in this work the project that led to the development of the Virtual Library of Emblem Books, showing its evolution from the beginning (simple search forms and answer pages) to its current state as a virtual library, focusing on the techniques used to build an intuitive and powerful user interface. Copyright © 2006 John Wiley & Sons, Ltd.