| المستخلص: |
لقد تم مؤخرا تعريف استعلام إيـــســبرج على أنه استعلام ذو أهمية كبيرة في كثير من التطبيقات. هذه الاستعلامات يمكن أن توصف بمدخلاتها الكبيرة الحجم ومخرجاتها القليلة. يشيرا أيسبرج إلى المدخلات وقمته تشير إلى المخرجات، وتقدم هذه الورقة خوارزمية فعالة لحساب نمط مهم من استعلام ايسبرج. تستعمل هذه الخوارزمية أسلوب التركيز على نتائج الاستعلام باستعمال طرق القياس الكمي. إن الخوارزمية الجديدة تكاد تتطلب دائما مسح البيانات مرتين أو أقل، وبذلك تكون الخوارزمية الجديدة أسرع من معظم الخوارزميات بمرتين أو أكثر، وتميز هذه الخوارزمية بصفات جيدة حيث أنها تتسع بشكل جيد مع حجم البيانات، كما أنها تتعامل مع أنواع متعددة لتوزيع البيانات، أما بالنسبة للذاكرة والمتطلبات الحسابية فهي صغيرة، إضافة إلى أنها الإدارة. وقد تم تقييم أداء الخوارزمية بناء على بيانات حقيقية ومصطنعة. إننا نعتقد أن الخوارزمية المقترحة هي الخيار الأفضل لحساب الاستعلامات المشمولة في هذه الورقة.
Iceberg queries have been recently identified as important queries for many applications. These queries can be characterized by their huge input-small output. The iceberg refers to the input, and the tip of it refers to the output. We present an efficient algorithm for computing an important class of iceberg queries. This algorithm uses a focusing technique for the query result using quantiling. The new algorithm almost always requires two or less scans over the input data, which outperforms other algorithms by a factor of two or more. It has several nice properties; it scales nicely with the data size; it is robust against the data distribution. Its memory and computational requirements are small. Further, it is easy to manage. We evaluate its performance using real and synthetic datasets. We believe that the presented algorithm is the algorithm of choice for computing the queries considered in this work.
|
