To see the other types of publications on this topic, follow the link: Skyline queries.
Dissertations / Theses on the topic 'Skyline queries'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 27 dissertations / theses for your research on the topic 'Skyline queries.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Fu, Gregory Chung Yin. "Skyline queries in database systems /." View Abstract or Full-Text, 2003. http://library.ust.hk/cgi/db/thesis.pl?COMP%202003%20FU.
Full textAbstract:
Thesis (M. Phil.)--Hong Kong University of Science and Technology, 2003.Includes bibliographical references (leaves 51-52). Also available in electronic version. Access restricted to campus users.
2
Gudala, Satyaveer Goud. "Skyline queries for multi-criteria decision support systems." Kansas State University, 2011. http://hdl.handle.net/2097/13250.
Full textAbstract:
Master of ScienceDepartment of Computing and Information Sciences
William H. Hsu
In decision-making applications, the Skyline query is used to find a set of non-dominated data points (called Skyline points) in a multi-dimensional dataset. A data point dominates another data point if it is at least as good as the other data point in all dimensions and better in at least one dimension. The skyline consists of data points not dominated by any other data point. Computing the skyline points of a dataset is essential for applications that involve multi-criteria decision making. Skyline queries filter out the interesting tuples from a potentially large dataset. No matter how we weigh our preferences along the attributes, only those tuples which score best under a monotone scoring function are part of the skyline. In other words, the skyline does not contain tuples which are nobody's favorite. With a growing number of real-world applications involving multi-criteria decision making over multiple dimensions, skyline queries can be used to answer those problems accurately and efficiently. This report mainly focuses on various skyline computing algorithms which can be used for online processing efficiently and are suitable to present multi-criteria decision making scenario. I implemented the Branch-and-Bound skyline Algorithm on two different data sets; one is a synthetic dataset and the other is a real dataset. My aim is to explore various subspaces of a given dataset and compute skylines over them, especially those subspace skylines which contain the least number of the skyline points.
3
Lampariello, Laura. "Indicatori originali per caratterizzare la rilevanza dei punti dello Skyline." Master's thesis, Alma Mater Studiorum - Università di Bologna, 2022.
Find full textAbstract:
La quantità sempre crescente di informazioni disponibili è uno dei maggiori problemi dei sistemi informativi di oggi. Oltre a restituire velocemente i risultati dell’interrogazione, è fondamentale fornire un accesso personalizzato e su misura all’utente finale.
Poiché gli attuali sistemi in uso (Query Top-k) presentano delle indubbie limitazioni, cioè non riescono fedelmente a interpretare i desideri dell’utente, si introducono per la prima volta dei nuovi indicatori. Questi nuovi indicatori, applicati ai punti estratti, caratterizzano tutti quei casi di “buon compromesso” che sono difficili da recuperare con interrogazioni Top-k. Essi vengono costruiti sui risultati di un’altra tipologia di interrogazione (Query Skyline) che non viene attualmente usata nei sistemi commerciali.
Gli originali indicatori, introdotti qui per la prima volta, sono tre: indice di concavità, robustezza alla griglia e incremento del volume di dominazione.
I risultati di questa trattazione potranno essere oggetto di lavori futuri volti all’ideazione di un nuovo e più valido tipo di query che possa sostituire più efficacemente quelle attuali.
4
Srivastava, Shweta. "Look Before You Leap: An Adaptive Processing Strategy For Multi-Criteria Decision Support Queries." Digital WPI, 2011. https://digitalcommons.wpi.edu/etd-theses/190.
Full textAbstract:
In recent years, we have witnessed a massive acquisition of data and increasing need to support multi-criteria decision support (MCDS) queries efficiently. Pareto-optimal also known as skyline queries is a popular class of MCDS queries and has received a lot of attention resulting in a flurry of efficient skyline algorithms. The vast majority of such algorithms focus entirely on the input being a single data set. In this work, we provide an adaptive query evaluation technique --- AdaptiveSky that is able to reason at different levels of abstraction thereby effectively minimizing the two primary costs, namely the cost of generating join results and the cost of dominance comparisons to compute the final skyline of the join results. Our approach hinges on two key principles. First, in the input space -- we determine the abstraction levels dynamically at run time instead of assigning a static one at compile time that may or may not work for different data distributions. This is achieved by adaptively partitioning the input data as intermediate results are being generated thereby eliminating the need to access vast majority of the input tuples. Second, we incrementally build the output space, containing the final skyline, without generating a single join result. Our approach is able to reason about the final result space and selectively drill into regions in the output space that show promise in generating result tuples to avoid generation of results that do not contribute to the query result. In this effort, we propose two alternate strategies for reasoning, namely the Euclidean Distance method and the cost-benefit driven Dominance Potential method for reasoning. Our experimental evaluation demonstrates that AdaptiveSky shows superior performance over state-of-the-art techniques over benchmark data sets.
5
Raghavan, Venkatesh. "Supporting Multi-Criteria Decision Support Queries over Disparate Data Sources." Digital WPI, 2012. https://digitalcommons.wpi.edu/etd-dissertations/120.
Full textAbstract:
In the era of "big data revolution," marked by an exponential growth of information, extracting value from data enables analysts and businesses to address challenging problems such as drug discovery, fraud detection, and earthquake predictions. Multi-Criteria Decision Support (MCDS) queries are at the core of big-data analytics resulting in several classes of MCDS queries such as OLAP, Top-K, Pareto-optimal, and nearest neighbor queries. The intuitive nature of specifying multi-dimensional preferences has made Pareto-optimal queries, also known as skyline queries, popular. Existing skyline algorithms however do not address several crucial issues such as performing skyline evaluation over disparate sources, progressively generating skyline results, or robustly handling workload with multiple skyline over join queries. In this dissertation we thoroughly investigate topics in the area of skyline-aware query evaluation. In this dissertation, we first propose a novel execution framework called SKIN that treats skyline over joins as first class citizens during query processing. This is in contrast to existing techniques that treat skylines as an "add-on," loosely integrated with query processing by being placed on top of the query plan. SKIN is effective in exploiting the skyline characteristics of the tuples within individual data sources as well as across disparate sources. This enables SKIN to significantly reduce two primary costs, namely the cost of generating the join results and the cost of skyline comparisons to compute the final results. Second, we address the crucial business need to report results early; as soon as they are being generated so that users can formulate competitive decisions in near real-time. On top of SKIN, we built a progressive query evaluation framework ProgXe to transform the execution of queries involving skyline over joins to become non-blocking, i.e., to be progressively generating results early and often. By exploiting SKIN's principle of processing query at multiple levels of abstraction, ProgXe is able to: (1) extract the output dependencies in the output spaces by analyzing both the input and output space, and (2) exploit this knowledge of abstract-level relationships to guarantee correctness of early output. Third, real-world applications handle query workloads with diverse Quality of Service (QoS) requirements also referred to as contracts. Time sensitive queries, such as fraud detection, require results to progressively output with minimal delay, while ad-hoc and reporting queries can tolerate delay. In this dissertation, by building on the principles of ProgXe we propose the Contract-Aware Query Execution (CAQE) framework to support the open problem of contract driven multi-query processing. CAQE employs an adaptive execution strategy to continuously monitor the run-time satisfaction of queries and aggressively take corrective steps whenever the contracts are not being met. Lastly, to elucidate the portability of the core principle of this dissertation, the reasoning and query processing at different levels of data abstraction, we apply them to solve an orthogonal research question to auto-generate recommendation queries that facilitate users in exploring a complex database system. User queries are often too strict or too broad requiring a frustrating trial-and-error refinement process to meet the desired result cardinality while preserving original query semantics. Based on the principles of SKIN, we propose CAPRI to automatically generate refined queries that: (1) attain the desired cardinality and (2) minimize changes to the original query intentions. In our comprehensive experimental study of each part of this dissertation, we demonstrate the superiority of the proposed strategies over state-of-the-art techniques in both efficiency, as well as resource consumption.
6
Alami, Karim. "Optimisation des requêtes de préférence skyline dans des contextes dynamiques." Thesis, Bordeaux, 2020. http://www.theses.fr/2020BORD0135.
Full textAbstract:
Les requêtes de préférence sont des outils intéressants pour calculer des sous-ensembles représentatifs d'ensembles de données en entrée ou pour classer les tuples en fonction des préférences des utilisateurs. Dans cette thèse, nous abordons principalement l'optimisation des requêtes Skyline, une classe spéciale des requêtes de préférence, dans des contextes dynamiques. Dans une première partie, nous abordons la maintenance incrémentale de la structure d'indexation multidimensionnelle NSC qui a été démontrée efficace pour répondre aux requêtes skyline dans un contexte statique. Plus précisément, nous abordons (i) le cas des données dynamiques, c'est-à-dire que des tuples sont insérés ou supprimés à tout moment, et (ii) le cas des données en streaming, c'est-à-dire que les tuples sont insérés et écartés après un intervalle de temps spécifique. En cas de données dynamiques, nous repensons la structure et proposons des procédures pour gérer efficacement les insertions et les suppressions. En cas de données en streaming, nous proposons MSSD un pipeline de données qui gère les données par lot et maintient NSCt une variation de NSC. Dans une deuxième partie, nous abordons le cas des ordres dynamiques, c'est-à-dire que certains ou tous les attributs de l'ensemble de données sont catégoriques et chaque utilisateur exprime son propre ordre partiel sur le domaine de ces attributs. Nous proposons des algorithmes parallèles évolutifs qui décomposent une requête en un ensemble de sous-requêtes et traitent chaque sous-requête indépendamment. Pour optimiser davantage, nous proposons la matérialisation partielle des sous-requêtes et introduisons le problème de la sélection de sous-requêtes en fonction d'un coûtPreference queries are interesting tools to compute small representatives of datasets or to rank tuples based on the users’ preferences. In this thesis, we mainly focus on the optimization of Skyline queries, a special class of preference queries, in dynamic contexts. In a first part, we address the incremental maintenance of the multidimensional indexing structure NSC which has been shown efficient for answering skyline queries in a static context. More precisely, we address (i) the case of dynamic data, i.e. tuples are inserted or deleted at any time, and (ii) the case of streaming data, i.e. tuples are appended only, and discarded after a specific interval of time. In case of dynamic data, we redesign the structure and propose procedures to handle efficiently both insertions and deletions. In case of streaming data, we propose MSSD a data pipeline which operates in batch mode, and maintains NSCt a variation of NSC. In a second part, we address the case of dynamic orders, i.e, some or all attributes of the dataset are nominal and each user expresses his/her own partial order on these attributes’ domain. We propose highly scalable parallel algorithms that decompose an issued query into a set of sub-queries and process each sub-query independently. In a further step for optimization, we propose the partial materialization of sub-queries and introduce the problem of cost-driven sub-queries selection
7
Elmi, Saïda. "An Advanced Skyline Approach for Imperfect Data Exploitation and Analysis." Thesis, Chasseneuil-du-Poitou, Ecole nationale supérieure de mécanique et d'aérotechnique, 2017. http://www.theses.fr/2017ESMA0011/document.
Full textAbstract:
Ce travail de thèse porte sur un modèle de requête de préférence, appelée l'opérateur Skyline, pour l'exploitation de données imparfaites. L'imperfection de données peut être modélisée au moyen de la théorie de l'évidence. Ce type de données peut être géré dans des bases de données imparfaites appelées bases de données évidentielles. D'autre part, l'opérateur skyline est un outil puissant pour extraire les objets les plus intéressants dans une base de données.Dans le cadre de cette thèse, nous définissons une nouvelle sémantique de l'opérateur Skyline appropriée aux données imparfaites modélisées par la théorie de l'évidence. Nous introduisons par la suite la notion de points marginaux pour optimiser le calcul distribué du Skyline ainsi que la maintenance des objets Skyline en cas d'insertion ou de suppression d'objets dans la base de données.Nous modélisons aussi une fonction de score pour mesurer le degré de dominance de chaque objet skyline et définir le top-k Skyline. Une dernière contribution porte sur le raffinement de la requête Skyline pour obtenir les meilleurs objets skyline appelés objets Etoile ou Skyline starsThe main purpose of this thesis is to study an advanced database tool named the skyline operator in the context of imperfect data modeled by the evidence theory. In this thesis, we first address, on the one hand, the fundamental question of how to extend the dominance relationship to evidential data, and on the other hand, it provides some optimization techniques for improving the efficiency of the evidential skyline. We then introduce efficient approach for querying and processing the evidential skyline over multiple and distributed servers. ln addition, we propose efficient methods to maintain the skyline results in the evidential database context wben a set of objects is inserted or deleted. The idea is to incrementally compute the new skyline, without reconducting an initial operation from the scratch. In the second step, we introduce the top-k skyline query over imperfect data and we develop efficient algorithms its computation. Further more, since the evidential skyline size is often too large to be analyzed, we define the set SKY² to refine the evidential skyline and retrieve the best evidential skyline objects (or the stars). In addition, we develop suitable algorithms based on scalable techniques to efficiently compute the evidential SKY². Extensive experiments were conducted to show the efficiency and the effectiveness of our approaches
8
Abidi, Amna. "Imperfect RDF Databases : From Modelling to Querying." Thesis, Chasseneuil-du-Poitou, Ecole nationale supérieure de mécanique et d'aérotechnique, 2019. http://www.theses.fr/2019ESMA0008/document.
Full textAbstract:
L’intérêt sans cesse croissant des données RDF disponibles sur le Web a conduit à l’émergence de multiple et importants efforts de recherche pour enrichir le formalisme traditionnel des données RDF à des fins d’exploitation et d’analyse. Le travail de cette thèse s’inscrit dans la continuation de ces efforts en abordant la problématique de la gestion des données RDF en présence d’imperfections (manque de confiance/validité, incertitude, etc.). Les contributions de la thèse sont comme suit: (1) Nous avons proposé d’appliquer l’opérateur skyline sur les données RDF pondérées par des mesures de confiance (Trust-RDF) dans le but d’extraire les ressources les plus confiantes selon des critères définis par l’utilisateur. (2) Nous avons discuté via des méthodes statistiques l’impact des mesures de confiance sur le Trust-skyline.(3) Nous avons intégré à la structure des données RDF un quatrième élément, exprimant une mesure de possibilité. Pour gérer cette mesure de possibilité, un cadre langagier appropriée est étudié, à savoir Pi-SPARQL, qui étend le langage SPARQL aux requêtes permettant de traiter des distributions de possibilités. (4) Nous avons étudié une variante d’opérateur skyline pour extraire les ressources RDF possibilistes qui ne sont éventuellement dominées par aucune autre ressource dans le sens de l’optimalité de ParetoThe ever-increasing interest of RDF data on the Web has led to several and important research efforts to enrich traditional RDF data formalism for the exploitation and analysis purpose. The work of this thesis is a part of the continuation of those efforts by addressing the issue of RDF data management in presence of imperfection (untruthfulness, uncertainty, etc.). The main contributions of this dissertation are as follows. (1) We tackled the trusted RDF data model. Hence, we proposed to extend the skyline queries over trust RDF data, which consists in extracting the most interesting trusted resources according to user-defined criteria. (2) We studied via statistical methods the impact of the trust measure on the Trust-skyline set.(3) We integrated in the structure of RDF data (i.e., subject-property-object triple) a fourth element expressing a possibility measure to reflect the user opinion about the truth of a statement.To deal with possibility requirements, appropriate framework related to language is introduced, namely Pi-SPARQL, that extends SPARQL to be possibility-aware query language.Finally, we studied a new skyline operator variant to extract possibilistic RDF resources that are possibly dominated by no other resources in the sense of Pareto optimality
9
Yuan, Yidong Computer Science & Engineering Faculty of Engineering UNSW. "Efficient computation of advanced skyline queries." 2007. http://handle.unsw.edu.au/1959.4/40511.
Full textAbstract:
Skyline has been proposed as an important operator for many applications, such as multi-criteria decision making, data mining and visualization, and user-preference queries. Due to its importance, skyline and its computation have received considerable attention from database research community recently. All the existing techniques, however, focus on the conventional databases. They are not applicable to online computation environment, such as data stream. In addition, the existing studies consider efficiency of skyline computation only, while the fundamental problem on the semantics of skylines still remains open. In this thesis, we study three problems of skyline computation: (1) online computing skyline over data stream; (2) skyline cube computation and its analysis; and (3) top-k most representative skyline. To tackle the problem of online skyline computation, we develop a novel framework which converts more expensive multiple dimensional skyline computation to stabbing queries in 1-dimensional space. Based on this framework, a rigorous theoretical analysis of the time complexity of online skyline computation is provided. Then, efficient algorithms are proposed to support ad hoc and continuous skyline queries over data stream. Inspired by the idea of data cube, we propose a novel concept of skyline cube which consists of skylines of all possible non-empty subsets of a given full space. We identify the unique sharing strategies for skyline cube computation and develop two efficient algorithms which compute skyline cube in a bottom-up and top-down manner, respectively. Finally, a theoretical framework to answer the question about semantics of skyline and analysis of multidimensional subspace skyline are presented. Motived by the fact that the full skyline may be less informative because it generally consists of a large number of skyline points, we proposed a novel skyline operator -- top-k most representative skyline. The top-k most representative skyline operator selects the k skyline points so that the number of data points, which are dominated by at least one of these k skyline points, is maximized. To compute top-k most representative skyline, two efficient algorithms and their theoretical analysis are presented.
10
Chia-HengChang and 張嘉恒. "Continuous Skyline Queries in Road Networks." Thesis, 2010. http://ndltd.ncl.edu.tw/handle/43915730531332275302.
Full textAbstract:
碩士國立成功大學
資訊工程學系碩博士班
98
The skyline query is an efficient tool for preference-based data analysis and attracts more attention than ever in the database community. Given a set of d-dimensional objects D, a skyline query retrieves all objects from D, which cannot be dominated by any others in D. In this paper, we investigate how to process the skyline query in road network, where the road distance between objects needs to be considered in query processing. Different from the previous related works, our work focuses on processing the continuous distance-based skyline query. We present two novel and important query types, named the Continuous d"-Skyline Query (Cd"-SQ for short) and the Continuous k nearest neighbor-Skyline Query (Cknn-SQ for short). To efficiently process the Cd"-SQ and Cknn-SQ in road network, we first design a grid index to manage the information of road network and objects, and then develop several algorithms combined with the grid index to determine the query result. Finally, we conduct a comprehensive set of experiments to demonstrate the effectiveness and the effciency of the proposed approaches.
11
Kuan-YingChiu and 邱冠穎. "Efficient Computation of Multiple Reverse Skyline Queries." Thesis, 2010. http://ndltd.ncl.edu.tw/handle/84303454806804219176.
Full textAbstract:
碩士國立成功大學
資訊工程學系碩博士班
98
The related issues of skyline query have become more popular in the past few years. Recently, many researchers have focused on the reverse skyline query because it is very useful in many applications, such as environment monitoring and commercial decision. In most applications of reverse skyline query, users consider several query points at the same time. The na?ve method for processing multiple query points is to deal with each query point one by one. Unfortunately, this method incurs significant cost for processing query. In this paper, we propose an efficient processing algorithm, named Concurrent Reverse Skyline algorithm (CRS), for reverse skyline query with multiple points. It takes into account the relationships not only between query points but also between query point and data. And a batch processing technique is used to lower the processing cost. Thus the CRS could reduce the average processing cost of each query point. The experiment results also show the efficiency and effectively of our proposed algorithm under various environments.
12
Su, Amber Hui-Zhu, and 蘇惠珠. "Continuous Probabilistic Skyline Queries over Uncertain Data Streams." Thesis, 2010. http://ndltd.ncl.edu.tw/handle/30912400976189651170.
Full textAbstract:
碩士國立清華大學
資訊工程學系
98
Recently, some approaches of finding probabilistic skylines on uncertain data have been proposed. In these approaches, a data object is composed of instances, each associated with a probability. The probabilistic skyline is then defined as a set of non-dominated objects with probabilities exceeding or equaling a given threshold. In many applications, data are generated as a form of continuous data streams. Accordingly, we make the first attempt to study a problem of continuously returning probabilistic skylines over uncertain data streams in this thesis. Moreover, the sliding window model over data streams is considered here. To avoid recomputing the probability of being not dominated for each uncertain object according to the instances contained in the current window, our main idea is to estimate the bounds of these probabilities for early determining which objects can be pruned or returned as results. We first propose a basic algorithm adapted from an existing approach of answering skyline queries on static and certain data, which updates these bounds by repeatedly processing instances of each object. Then, we design a novel data structure to keep dominance relation between some instances for rapidly tightening these bounds, and propose a progressive algorithm based on this new structure. Moreover, these two algorithms are also adapted to solve the problem of continuously maintaining top-k probabilistic skylines. Finally, a set of experiments are performed to evaluate these algorithms, and the experiment results reveal that the progressive algorithm much outperforms the basic one, directly demonstrating the effectiveness of our newly designed structure.
13
kuan-chieh, Huang, and 黃冠捷. "A study for multiple constrained skyline queries processing." Thesis, 2014. http://ndltd.ncl.edu.tw/handle/66953880343640440938.
Full textAbstract:
碩士長榮大學
資訊管理學系(所)
102
In this paper, we propose a constrained skyline query processing algorithms. This algorithm is named GCSQP. Compare with preview methods, GCSQP will merge and process them afterward . The advantage is that after the merger operation, GCSQP can save a lot of time to perform dominance test operation, thereby accelerating query processing efficiently. In this paper, we propose a GCSQP design concept, explain the details of the algorithm, and perform multiple experiments to prove that GCSQP can indeed accelerate query processing efficiently on constrained skyline query.
14
Liou, Meng-zong, and 劉孟宗. "A Study on Skyline Queries for GPGPU Computing." Thesis, 2014. http://ndltd.ncl.edu.tw/handle/17767213546033845639.
Full textAbstract:
碩士國立臺灣科技大學
電子工程系
102
Skyline query finds some special points from data, called skyline points, those are irreplaceable and help us making decision or using in data mining. Skyline query result size and execution time are rapid growth as number of components increasing, therefore some researcher using parallelism to improve this problem, but limited effect by framework hardware, like multi-core or distributed environment. This paper studies skyline query in general-purpose computing on graphics processing units (GPGPU) framework and proposes GPGPU skyline query (GSQ) algorithm, using filter method to reduce the number of data comparisons, in final simulation, GSQ is compared with other algorithms and we find GSQ is most effective in most cases. II
15
楊朝文. "Efficient Computation of Group Skyline Queries on MapReduce." Thesis, 2015. http://ndltd.ncl.edu.tw/handle/78635141893454416924.
Full textAbstract:
碩士逢甲大學
資訊工程學系
103
Skyline query is one of the important issues in database research and has been applied in diverse applications including multi-criteria decision support systems and so on. The response of a skyline query eliminates unnecessary tuples and returns only the user-interested result. Traditional skyline query picks out the outstanding tuples, based on one-to-one record comparisons. Some modern applications request, beyond the singular ones, for superior combinations of records. For example, fantasy basketball is composed of 5 players, fantasy baseball of 9 players, and a hackathon of several programmers. Group skyline aims at considering all the groups comprising several records, and finding out the non-dominated ones. In comparison to skyline query, group skyline query has much higher computational complexity. Given a dataset of 100 players, skyline query deals with the one-to-one comparisons between the 100 tuples, while group skyline needs to pick out the superior ones from the 7.5 million combinations with respect to a team of 5 players. Because of the high complexity, few studies have been conducted and none has been presented in either distributed or parallel computing. This thesis is the first study that solves the group skyline in the distributed MapReduce framework. We propose the MRGS algorithm to generate all the combinations, compute the winners at each local node, and find out the answer globally. We further propose the MRIGS algorithm to release the bottleneck of MRGS on unbalanced computing load of nodes. Finally, we propose the MRIGS-P algorithm to prune the impossible combinations and produce indexed and balanced MapReduce computation. Extensive experiments with NBA datasets show that MRIGS-P is 6 times faster than the MRGS algorithm.
16
Zong-HanHe and 何宗翰. "Continuous kNN-Skyline Queries over Moving Objects with Uncertainty." Thesis, 2012. http://ndltd.ncl.edu.tw/handle/37085470739703321905.
Full textAbstract:
碩士國立成功大學
資訊工程學系碩博士班
100
Continuous k nearest neighbor-skyline query (CkNN-SQ) is an important type of spatio-temporal queries. Given a query time interval [ts, te] and a moving query object q, a CkNN-SQ is to retrieve the k-nearest neighbor skyline points (kNN-SP) of q at each time instant within [ts, te]. Different from the previous works, our work devotes to overcoming the past assumption that each object is static with certain dimensional values and located in road networks. In this paper, we focus on processing the CkNN-SQ over moving objects with uncertain dimensional values in Euclidean space and the velocity of each object (including the query object) varies within a known range. Such a query is called the continuous possible-kNN-skyline query (CPkNN-SQ). We first discuss the difficulties raised by the uncertainty of object and then propose the CPkNN-SQ algorithm operated with a data-partitioning index, called the uncertain TPR-tree (UTPR-tree), to efficiently answer the CPkNN-SQ. Comprehensive experiments are performed to demonstrate the effectiveness and the efficiency of the proposed approach.
17
Hung, Jen-Tso, and 洪任佐. "A Study for Continuous Skyline Queries in Road Networks." Thesis, 2014. http://ndltd.ncl.edu.tw/handle/x2nd85.
Full textAbstract:
碩士國立臺北科技大學
資訊工程系研究所
102
Skyline query returns objects that are not being dominated in the data set, many of the contributions to compute skyline query such as bit-map and divide-and-conquer has been proposed, we also call this kind of query as snapshot skyline query since their results are static, but nowadays those snapshot skyline query seems not enough for real-world situation, they don’t meet our new requirements which people needs to get the real-time results while moving, for example: one may request when driving, therefore we need to observe the results to ensure that its correct in most of the time, in contrast to snapshot skyline query, this kind of query is known as continuous skyline query. Due to the popularity of mobile devices, researches of continuous query such as continuous nearest neighbor query, continuous k nearest neighbor query, and continuous skyline query have been taken more attention than before; in this paper, we will focus on continuous skyline query. Exists approaches such as prediction methods, safe region can well handle the skyline result continuously, in contrast, our approach can be easily implement on different environment by changing its update timing, we will introduce the way to implement our algorithms on both Euclidean space and real-world road networks; the advantages and disadvantages can be seem through experiments.
18
CHEN, KUAN-LUN, and 陳冠綸. "Efficient Processing of Skyline-Join Queries without Dominance Checking." Thesis, 2017. http://ndltd.ncl.edu.tw/handle/19005421112530443567.
Full textAbstract:
碩士逢甲大學
資訊工程學系
105
Skyline query has been actively studied in database research. The query performs dominance checking among tuples according to user preferences and returns only the interesting ones. The complexity of finding skyline tuples increases as the number of dimensions of the relation increases, so that most of the studies focus on improving the performance of skyline query on a single relation. In practice, many applications require skyline queries on a relation produced by joining two or more relations, called skyline-join queries. Joining the skyline results of the two relations cannot produce the final skyline. Efficient processing of skyline-join queries thus becomes more important as the increased number of tuples and the increased number of dimensions from join will exacerbate the skyline finding. Previous studies used strategies to prune tuples before join and reduce the number of dominance checks after join. In this study, we propose a novel algorithm called SWID (Skyline-join without dominance checking) to solve the problem efficiently. The SWID algorithm partitions relations and prunes impossible tuples first, finds local skylines in each group of tuples of same join attribute, constructs group identifications for tuples that might become part of the final skyline, and generates directly the final result by cross-products between partitions without any dominance checks after join. Our experiments using synthetic datasets and real datasets show that the SWID algorithm is more than 100 times faster than the SEPT algorithm and 64 times faster than the MSC algorithm in average. In addition, the SWID algorithm has excellent linear scalability.
19
Tseng, Kuo-Chen, and 曾國禎. "Efficient Algorithms of Equivalent Ranges Computations for Reverse Skyline Queries." Thesis, 2011. http://ndltd.ncl.edu.tw/handle/49275614625641125413.
Full textAbstract:
碩士逢甲大學
資訊工程所
99
Skyline queries are receiving much attention recently because of its wide applicability in multi-criteria decision-making and user-preference applications. A skyline query returns only the data objects, called skyline points, in a set that are not dominated by any other data object on all dimensions. Occasionally, the interested skyline needs to be computed with respect to a user-specified data point, such a query is referred to as a dynamic skyline query. Based on the idea of dynamic skyline queries, a reverse skyline query finds out the set of data points whose dynamic skyline contains the reference data point. The result of a reverse skyline query can be used by a provider to understand the potential customers, showing their interested products as data points, with respect to a reference product-point. In this thesis, we propose the EquRanger algorithm to find the equivalent range of a selected attribute for the reference point in a reverse skyline query. The provider may use any value in the equivalent range to substitute the original value for this attribute and obtain a new reference point, named equivalent point. Particularly, the reverse skyline of the equivalent point is the same set or a superset of the original reverse skyline. Thus, the provider may benefit from presenting the new reference product without losing any original potential customer. Furthermore, we also propose the MaxRanger algorithm to find out a combination of the maximum value for each attribute. The combination sets the attribute values of multiple domains altogether to generate a maximum profitable equivalent point. Extensive experiments show that the proposed algorithms may efficiently discover the equivalent ranges and maximum profitable equivalent points in reverse skyline computations.
20
林靖琨. "Efficient Processing of Skyline Queries in Aggregate-Join with Constraints." Thesis, 2016. http://ndltd.ncl.edu.tw/handle/a7p3qv.
Full textAbstract:
碩士逢甲大學
資訊工程學系
104
Skyline query is an important issue in database research. The query uses a dominance relationship to return an interesting set, called skyline, for the user. Previous researches usually assume that the skyline query is applied on a single table only. However, table join is so common in database queries that finding the skyline in joining tables, called skyline join, becomes an essential problem. The problem of finding the skyline in a single table of high dimension is complicated so that the algorithms for solving skyline joins hardly can be found. In practice, table join often generates a new attribute by aggregation, and a user generally specifies a constraint on the aggregated attribute for the skyline join. For example, finding the skyline of joining a hotel table and a restaurant table on the same location for best hotel-restaurant combinations usually comes with a budget on the total price; business trips travelling across cities would be constrained in the total travelling distance after joining the traffic tables on the same city for finding the best travelling plan; finding best sales for product bundling demands skyline join on the production area with a constraint of total production time. Thus, discovering skylines in aggregate-join with constraints is more important in practice. In this thesis, we propose an algorithm called SAJC (Skyline in Aggregate-Join with Constraints) to solve the problem. SAJC uses sorting and early-pruning techniques to eliminate data before aggregate-join. SAJC then uses a constrained-join technique to reduce the tuples in the join and computes the answer by the dominance-check technique. Our comprehensive experiments using synthetic datasets and real datasets show that SAJC is 9 to 40 times faster than the SEPT algorithm, 2 times faster than the MSC algorithm in average, and has excellent scalability.
21
Mumpuni, Retno, and 馬佩妮. "A Grid-Based Approach to Answer Tolerance-Based Skyline Queries." Thesis, 2015. http://ndltd.ncl.edu.tw/handle/04681257345826560500.
Full textAbstract:
碩士國立臺灣科技大學
資訊工程系
103
This thesis introduces a new grid-based approach to solve tolerance-based skyline queries. Tolerance-based skyline queries is relatively new problem where the notion of tolerance margin is introduced previously as user preferences for the skyline query, which also serves to relax the rigidness of the classic skyline. The properties of the tolerance-based dominance relation is reviewed and investigated in this thesis. In particular, the relationship between traditional pareto-dominance and tolerance-based dominance relations is studied in depth. We then exploit this relationship along with grid properties to present an efficient grid-based scheme for processing a tolerance-based skyline with arbitrary tolerance tuple. Our algorithm essentially converts the tolerance-based skyline query processing operation into simple pareto-based dominance checking over grid space. Extensive experiments have been conducted to evaluate the performance of the proposed method.
22
"Efficient Processing of Skyline Queries on Static Data Sources, Data Streams and Incomplete Datasets." Doctoral diss., 2014. http://hdl.handle.net/2286/R.I.27470.
Full textAbstract:
abstract: Skyline queries extract interesting points that are non-dominated and help paint the bigger picture of the data in question. They are valuable in many multi-criteria decision applications and are becoming a staple of decision support systems.
An assumption commonly made by many skyline algorithms is that a skyline query is applied to a single static data source or data stream. Unfortunately, this assumption does not hold in many applications in which a skyline query may involve attributes belonging to multiple data sources and requires a join operation to be performed before the skyline can be produced. Recently, various skyline-join algorithms have been proposed to address this problem in the context of static data sources. However, these algorithms suffer from several drawbacks: they often need to scan the data sources exhaustively to obtain the skyline-join results; moreover, the pruning techniques employed to eliminate tuples are largely based on expensive tuple-to-tuple comparisons. On the other hand, most data stream techniques focus on single stream skyline queries, thus rendering them unsuitable for skyline-join queries.
Another assumption typically made by most of the earlier skyline algorithms is that the data is complete and all skyline attribute values are available. Due to this constraint, these algorithms cannot be applied to incomplete data sources in which some of the attribute values are missing and are represented by NULL values. There exists a definition of dominance for incomplete data, but this leads to undesirable consequences such as non-transitive and cyclic dominance relations both of which are detrimental to skyline processing.
Based on the aforementioned observations, the main goal of the research described in this dissertation is the design and development of a framework of skyline operators that effectively handles three distinct types of skyline queries: 1) skyline-join queries on static data sources, 2) skyline-window-join queries over data streams, and 3) strata-skyline queries on incomplete datasets. This dissertation presents the unique challenges posed by these skyline queries and addresses the shortcomings of current skyline techniques by proposing efficient methods to tackle the added overhead in processing skyline queries on static data sources, data streams, and incomplete datasets.Dissertation/Thesis
Doctoral Dissertation Computer Science 2014
23
黃美瑄. "Top-K Subspace Skyline Queries with Ranking on High Dimensional Data." Thesis, 2013. http://ndltd.ncl.edu.tw/handle/07974041029309325994.
Full text
24
Yi-ChungChen and 陳奕中. "A Study on Enhancing the Efficiency and Applicability of Skyline Queries." Thesis, 2014. http://ndltd.ncl.edu.tw/handle/j874pz.
Full textAbstract:
博士國立成功大學
資訊工程學系
102
Multi-criteria searching technique has attracted a great deal of attention in recent years. In our work, we focus on the skyline queries and its extensions for evaluating such multi-criteria searching results. Given a set of data points in a multidimensional database, such queries return points that are not “dominated” (detailed in this thesis) by any other point. This thesis is divided into two parts. The first part introduces three problems that arise during the execution of a skyline query or its extension. They are the problems caused by the excessive quantity of data in databases, the inability of processing a skyline query in databases with unquantifiable dimensions, and the inefficiency of processing a subspace skyline query. The second part of the thesis addresses the issue of how a skyline query can be incorporated into new environments, including the distributed client-server environment and the spatio-temporal database environment. Novel solutions to these problems are presented in this thesis. All proposed algorithms are analyzed and simulated through extensive experiments. The results indicate that they are effective in supporting a skyline query and its applications mentioned in this thesis.
25
Kuo-BinYuan and 袁國斌. "Efficient Processing of Continuous Skyline Queries with Updates in Road Networks." Thesis, 2011. http://ndltd.ncl.edu.tw/handle/55269535458681357502.
Full text
26
Lee, Tsai-Min, and 李蔡旻. "Processing Range and Skyline Queries using Voronoi Diagram in Wireless Broadcasting Environment." Thesis, 2014. http://ndltd.ncl.edu.tw/handle/yhn56a.
Full textAbstract:
碩士國立臺北科技大學
資訊工程系研究所
102
Data broadcasting is an effective way to disseminate information to a large amount of mobile clients in wireless mobile environment. The skyline search is one practical query in multi-criterion local based services. But skyline search may return some useless result which location is far away from query point. Although the data is skyline, it helpless for user. So our protocol not only consider the dominate relation-ship but also consider the distance between skyline result and query point. Our protocol combines range query and skyline query to reach the objective and return the skyline result which is also the range query result. This paper consider the influence of scheduling in data broadcasting cycle and discuss the latency and tuning time among different scheduling approaches. This paper also discuss how to combine range query and skyline query lead to better performance, and explain the correctness of our protocol.
27
Jiang, Bin Computer Science & Engineering Faculty of Engineering UNSW. "Probabilistic skylines on uncertain data." 2007. http://handle.unsw.edu.au/1959.4/40712.
Full textAbstract:
Skyline analysis is important for multi-criteria decision making applications. The data in some of these applications are inherently uncertain due to various factors. Although a considerable amount of research has been dedicated separately to efficient skyline computation, as well as modeling uncertain data and answering some types of queries on uncertain data, how to conduct skyline analysis on uncertain data remains an open problem at large. In this thesis, we tackle the problem of skyline analysis on uncertain data. We propose a novel probabilistic skyline model where an uncertain object may take a probability to be in the skyline, and a p-skyline contains all the objects whose skyline probabilities are at least p. Computing probabilistic skylines on large uncertain data sets is challenging. An uncertain object is conceptually described by a probability density function (PDF) in the continuous case, or in the discrete case a set of instances (points) such that each instance has a probability to appear. We develop two efficient algorithms, the bottom-up and top-down algorithms, of computing p-skyline of a set of uncertain objects in the discrete case. We also discuss that our techniques can be applied to the continuous case as well. The bottom-up algorithm computes the skyline probabilities of some selected instances of uncertain objects, and uses those instances to prune other instances and uncertain objects effectively. The top-down algorithm recursively partitions the instances of uncertain objects into subsets, and prunes subsets and objects aggressively. Our experimental results on both the real NBA player data set and the benchmark synthetic data sets show that probabilistic skylines are interesting and useful, and our two algorithms are efficient on large data sets, and complementary to each other in performance.