Title :
An External Memory Algorithm of Maxima-Finding Problems
Author :
Gui, Xiang-Quan ; Zhang, Yuan-ping ; Li, Li ; Yong, Xue-rong
Author_Institution :
Coll. of Comput. & Commun., Lanzhou Univ. of Technol., Lanzhou
Abstract :
Maxima-finding problems are the fundamental problem in computational geometry with a great deal of application in many areas, and it has resurfaced with the advent of Skyline Queries for relational databases and data mining recently. The existed algorithms in the field of Maxima-finding problem (Skyline Queries) have been summarized in this paper. But for the massive data sets, there has no I/O linear algorithm yet. A new kind of External Memory Algorithm of Maxima-finding problem (EMMF) has been presented, the I/O complexity of algorithm is linear, the corresponding reliability has been validated from experiments, and the status of 2-dimensional space has been proved in theory too.
Keywords :
data mining; relational databases; storage management; 2-dimensional space; I/O complexity; Skyline Queries; computational geometry; data mining; external memory algorithm; maxima-finding problems; relational databases; Computational geometry; Computer science; Computer science education; Costs; Data mining; Educational institutions; Educational technology; Electronic mail; Reliability theory; Sorting; I/O algorithm; Maxima-finding problem; Skyline query; external memory algorithm;
Conference_Titel :
Education Technology and Computer Science, 2009. ETCS '09. First International Workshop on
Conference_Location :
Wuhan, Hubei
Print_ISBN :
978-1-4244-3581-4
DOI :
10.1109/ETCS.2009.439
