A multicomputer query processing model for full-text retrieval using compressed bitmaps
Hurriyet Aydin Ok · 1994
This research: (1) investigates the impact of using inverted files constructed with compressed bit-vectors on disk space utilization and query processing time, in a full-text retrieval environment; and (2) describes a multicomputer system, intended for text retrieval, to improve query response time using the compressed bit-vectors approach. The dissertation defines a composite compression scheme for bit-vectors based on exponential-Golomb encoding. The composite scheme is applied to a synthetic inverted index that was modeled using the USA Today Online News Database. It is shown that the inverted file of the modeled index can be reduced to 36 percent of its original size by using the composite compression scheme. It is demonstrated by simulation that the compression scheme may decrease the response time by a factor of 2 on average, compared to an inversion list implementation of the inverted file. It was assumed that the queries are processed by a 20 MIPS, single CPU, single disk computer. Parallel query processing becomes indispensable when retrieving documents within a tolerable time from a large document database. This work presents a scalable multicomputer architecture for fast query handling in two stages: (1) retrieves a list of documents that are possibly relevant to the query by comparing compressed bit-vectors in parallel; (2) searches for each query term in the documents reported by the first stage, and returns a list of documents satisfying the term proximity rules supplied by the query. It is shown by simulation that the first stage response time may be kept below 1 second by using several computers connected through a local network, for varying workload characteristics, such as increased query arrival rate, or more terms per query. Second stage operations are analyzed by using quantitative techniques. The I/O intensive second stage operations become a bottleneck even for light query loads. Thus, by using multiple processors and disks for the second stage, overall query processing time can be accomplished in under 3 seconds for query loads with 10-200 terms per query, 10 queries per second, and possibly relevant documents lists averaging 108 documents per query.