The Optimality of Allocation Methods for Bounded Disagreement Search Queries: The Possible and the Impossible
Pages 1194 - 1206
Abstract
Data Allocation on multiple I/O devices manifests itself in many computing systems, both centralized and distributed. Data is partitioned on multiple I/O devices and clients issue various types of queries to retrieve relevant information. In this paper, we derive necessary and sufficient conditions for a data allocation method to be optimal for two important types of queries: partial match and bounded disagreement search queries. We formally define these query types and derive the optimality conditions based on coding-theoretic arguments. Although these conditions are fairly strict, we show how to construct good allocation methods for practical realistic situations. Not only are the response times bounded by a small value, but also the identification of the relevant answer set is efficient.
References
[1]
Khaled A. S. Abdel-Ghaffar, Amr El Abbadi, Optimal disk allocation for partial match queries, ACM Transactions on Database Systems (TODS), v.18 n.1, p.132-156, March 1993
[2]
M.J. Atallah and S. Prabhakar, “(Almost) Optimal Parallel Block Access for Range Queries,” Proc. ACM Symp. Principles of Database Systems, pp. 205-215, May 2000.
[3]
E.R. Berlekamp, Algebraic Coding Theory. Laguna Hills, Calif.: Aegean Park Press, 1984.
[4]
R. Bhatia, R.K. Sinha, and C.-M. Chen, “Hierarchical Declustering Schemes for Range Queries,” Proc. Int'l Conf. Extending Database Technology, pp. 525-537, Mar. 2000.
[5]
A. Borodin, R. Ostrovsky, and Y. Rabani, “Lower Bounds for High Dimensional Nearest Neighbor Search and Related Problems,” Proc. ACM Symp. Theory of Computing, pp. 312-321, May 1999.
[6]
C.-M. Chen and C.T. Cheng, “From Discrepancy to Declustering: Near-Optimal Multidimensional Declustering Strategies for Range Queries,” J. ACM, vol. 51, no. 1, pp. 46-73, 2004.
[7]
H. C. Du, J. S. Sobolewski, Disk allocation for Cartesian product files on multiple-disk systems, ACM Transactions on Database Systems (TODS), v.7 n.1, p.82-101, March 1982
[8]
IEEE Trans. Software Eng., vol. 14, no. 10, pp. 1381-1393, Oct. 1988.
[9]
C. Faloutsos and D. Metaxas, “Declustering Using Error Correcting Codes,” Proc. ACM Symp. Principles of Database Systems, pp. 253-258, Mar. 1989.
[10]
V. Guruswami, “List Decoding of Error-Correcting Codes,” PhD thesis, MIT, 2001.
[11]
V. Guruswami and M. Sudan, “Improved Decoding of Reed-Solomon and Algebraic-Geometry Codes,” IEEE Trans. Information Theory, vol. 45, pp. 1757-1767, Sept. 1999.
[12]
Joseph M. Hellerstein, Elias Koutsoupias, Daniel P. Miranker, Christos H. Papadimitriou, Vasilis Samoladas, On a model of indexability and its bounds for range queries, Journal of the ACM (JACM), v.49 n.1, p.35-55, January 2002
[13]
IEEE Trans. Information Theory, vol. 8, no. 32, pp. 203-207, 1962.
[14]
H.C. Kim and K.-J. Li, “Declustering Spatial Objects by Clustering for Parallel Disks,” Proc. Int'l Conf. Database and Expert Systems Applications, pp. 450-459, Sept. 2001.
[15]
M.H. Kim and S. Pramanik, “Optimal File Distribution for Partial Match Retrieval,” Proc. ACM SIGMOD Int'l Conf. Management of Data, pp. 173-182, June 1988.
[16]
S. Kuo, M. Winslett, Y. Cho, and J. Lee, “New GDM-Based Declustering Methods for Parallel Range Queries,” Proc. Int'l Database Eng. and Applications Symp., pp. 119-127, Aug. 1999.
[17]
IEEE Trans. Knowledge Data Eng., vol. 10, no. 2, pp. 310-327, Mar./Apr. 1998.
[18]
Information and Control, vol. 11, pp. 613-616, 1967.
[19]
R.L. Rivest, “Partial-Match Retrieval Algorithms,” SIAM J. Computing, vol. 5, pp. 19-50, Mar. 1976.
[20]
R.K. Sinha, R. Bhatia, and C.-M. Chen, “Asymptotically Optimal Declustering Schemes for Range Queries,” Proc. Int'l Conf. Database Theory, pp. 144-158, Jan. 2001.
[21]
IEEE/ACM Trans. Networking, vol. 11, no. 1, pp. 17-32, Feb. 2003.
[22]
J.H. van Lint, Introduction to Coding Theory, third ed. Berlin: Springer, 1999.
[23]
IEEE Trans. Information Theory, vol. 33, no. 5, pp. 665-680, 1987.
Index Terms
- The Optimality of Allocation Methods for Bounded Disagreement Search Queries: The Possible and the Impossible
Recommendations
Optimal disk allocation for partial match queries
The problem of disk allocation addresses the issue of how to distribute a file on several disks in order to maximize concurrent disk accesses in response to a partial match query. In this paper a coding-theoretic analysis of this problem is presented, ...
Minimum cost selection of secondary indexes for formatted files
Secondary indexes are often used in database management systems for secondary key retrieval. Although their use can improve retrieval time significantly, the cost of index maintenance and storage increases the overhead of the file processing application. ...
Disk allocation for Cartesian product files on multiple-disk systems
Cartesian product files have recently been shown to exhibit attractive properties for partial match queries. This paper considers the file allocation problem for Cartesian product files, which can be stated as follows: Given a k-attribute Cartesian ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2006.
Publisher
IEEE Educational Activities Department
United States
Publication History
Published: 01 September 2006
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 03 Nov 2024