Partial evaluation of queries for bit-sliced signature files

✍ Scribed by Seyit Kocberber; Fazli Can

• Book ID: 104137300
• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 642 KB
• Volume: 60
• Category: Article
• ISSN: 0020-0190
• DOI: 10.1016/s0020-0190(96)00176-7

✦ Synopsis

Our research extends the bit-sliced signature organization by introducing a partial evaluation approach for queries. The partial evaluation approach minimizes the response time by using a subset of the on-bits of the query signature. A new signature file optimization method, Partially evaluated Bit-Sliced Signature File (P-BSSF), for multi-term query environments using the partial evaluation approach is introduced. The analysis shows that, with 14% increase in space overhead, P-BSSF provides a query processing time improvement of more than 85% for multi-term query environments with respect to the best performance of the bit-sliced signature file (BSSF) method. Under the sequentiality assumption of disk blocks, P-BSSF provides a desirable response time of 1 second for a database size of one million records with a 28% space overhead. Due to partial evaluation, the desirable response time is guaranteed for queries with several terms.