检索结果-内蒙古大学图书馆

Efficient Representative Subset Selection over Sliding Windows

IEEE TRANSACTIONS ON KNOWLEDGE AND data ENGINEERING 2019年第7期31卷 1327-1340页

作者： Wang, Yanhao Li, Yuchen Tan, Kian-Lee Natl Univ Singapore Sch Comp Singapore 117417 Singapore Singapore Management Univ Sch Informat Syst Singapore 178902 Singapore

Representative subset selection (RSS) is an important tool for users to draw insights from massive datasets. Existing literature models RSS as the submodular maximization problem to capture the "diminishing returns" property of the representativeness of selected subsets, but often only has a single constraint (e.g., cardinality), which limits its applications in many real-world problems. To capture the data recency issue and support different types of constraints, we formulate dynamic RSS in data streams as maximizing submodular functions subject to general d-knapsack constraints (SMDK) over sliding windows. We propose a KNAPWINDOW framework (KW) for SMDK. KW utilizes the KNAPSTREAM algorithm (KS) for SMDK in append-only streams as a subroutine. It maintains a sequence of checkpoints and KS instances over the sliding window. Theoretically, KW is 1-epsilon/1+dapproximate for SMDK. Furthermore, we propose a KNAPWINDOWPLUS framework (KW+) to improve upon KW. KW+ builds an index SUBKNAPCHK to manage the checkpoints and KS instances. SUBKNAPCHK deletes a checkpoint whenever it can be approximated by its successors. By keeping much fewer checkpoints, KW+ achieves higher efficiency than KW while still guaranteeing a 1-epsilon'/2+2d-approximate solution for SMDK. Finally, we evaluate the efficiency and solution quality of KW and KW+ in real-world datasets. The experimental results demonstrate that KW achieves more than two orders of magnitude speedups over the batch baseline and preserves high-quality solutions for SMDK over sliding windows. KW+ further runs 5-10 times faster than KW while providing solutions with equivalent or even better utilities.

关键词： data summarization sliding window data stream submodular maximization approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Querying a summary of database

引用

JOURNAL OF INTELLIGENT INFORMATION SYSTEMS 2006年第1期26卷 59-73页

作者： Voglozin, WA Raschia, G Ughetto, L Mouaddib, N Univ Nantes Lab Informat Nantes Atlantique F-44322 Nantes 3 France

For some years, data summarization techniques have been developed to handle the growth of databases. However these techniques are usually not provided with tools for end-users to efficiently use the produced summaries. This paper presents a first attempt to develop a querying tool for the SAINTETIQ summarization model. The proposed search algorithm takes advantage of the hierarchical structure of the SAINTETIQ summaries to efficiently answer questions such as "how are, on some attributes, the tuples which have specific characteristics?" Moreover, this algorithm can be seen both as a boolean querying mechanism over a hierarchy of summaries, and as a flexible querying mechanism over the underlying relational tuples.

关键词： data summarization linguistic summaries summary querying relational database flexible querying fuzzy labels

来源：评论

学校读者我要写书评

暂无评论

Specification and management of interdependent data in operational systems and data warehouses

引用

DISTRIBUTED AND PARALLEL dataBASES 1997年第2期5卷 121-166页

作者： Georgakopoulos, D Karabatis, G Gantimahapatruni, S BELLCORE MORRISTOWNNJ 07960 SYBASE INC EMERYVILLECA 94608

(Inter)Dependent objects include data replicated or cached in multiple database systems, data collected and summarized in data warehouses for analysis, planning, and decision support, as well as any other category of objects whose states are related and they are maintained in different information systems. In this paper we discuss dependencies between objects in an environment consisting of operational systems and a data warehouse, and describe their specification and enforcement. To specify object dependencies we introduce Object Dependency Descriptors (ObjectDDs). These describe the relationships between dependent objects, and define how much inconsistency between original objects and their replicas/collections/summaries can be tolerated before it is necessary to restore their consistency. Object dependencies are enforced by extended transactions designed specifically for evaluating if dependent objects satisfy their specified relationships, evaluating whether possible inconsistencies can be tolerated, and (if not) restoring consistency. To describe the transactional behavior of such consistency evaluation and restoration transactions we use Transaction Dependency Descriptors (TransactionDDs). TransactionDDs define the transactional relationships between consistency evaluation and restoration (asynchronous) transactions, as well as the relationships between such asynchronous transactions and regular (synchronous) transactions executed directly by applications. To automatically maintain the consistency of dependent objects, we propose the concept of a Dependency Management System (DMS). A DMS monitors dependent objects, evaluates object consistency, and schedules and controls consistency restoration transactions to keep dependent objects within acceptable consistency levels. We describe key components in the DMS architecture, and a relatively simple implementation involving straightforward extensions in a relational DBMS.

关键词： data replication data summarization asynchronous transactions ECA rules activity models extended transactions

来源：评论

学校读者我要写书评

暂无评论

A Unified Approach to Coreset Learning

引用

IEEE TRANSACTIONS ON NEURAL NETWORKS AND LEARNING SYSTEMS 2024年第5期35卷 6893-6905页

作者： Maalouf, Alaa Eini, Gilad Mussay, Ben Feldman, Dan Osadchy, Margarita Univ Haifa Dept Comp Sci IL-3498838 Haifa Israel

Coreset of a given dataset and loss function is usually a small weighed set that approximates this loss for every query from a given set of queries. Coresets have shown to be very useful in many applications. However, coresets construction is done in a problem dependent manner and it could take years to design and prove the correctness of a coreset for a specific family of queries. This could limit coresets use in practical applications. Moreover, small coresets provably do not exist for many problems. To address these limitations, we propose a generic, learning-based algorithm for construction of coresets. Our approach offers a new definition of coreset, which is a natural relaxation of the standard definition and aims at approximating the \emph{average} loss of the original data over the queries. This allows us to use a learning paradigm to compute a small coreset of a given set of inputs with respect to a given loss function using a training set of queries. We derive formal guarantees for the proposed approach. Experimental evaluation on deep networks and classic machine learning problems show that our learned coresets yield comparable or even better results than the existing algorithms with worst-case theoretical guarantees (that may be too pessimistic in practice). Furthermore, our approach applied to deep network pruning provides the first coreset for a full deep network, i.e., compresses all the network at once, and not layer by layer or similar divide-and-conquer methods.

关键词： Training Standards Q measurement Machine learning algorithms Computational modeling Weight measurement Support vector machines Coresets data summarization generalization learning

来源：评论

学校读者我要写书评

暂无评论

Hash function design for cloud storage data auditing

引用

THEORETICAL COMPUTER SCIENCE 2019年 800卷 42-51页

作者： Doukas, Nikolaos Markovskyi, Oleksandr P. Bardis, Nikolaos G. Hellen Mil Acad Dept Math & Engn Sci Vari 16673 Greece Natl Tech Univ Ukraine Dept Comp Engn Polytech Inst Kiev KPI 2003 UA-252056 Kiev Ukraine

Cloud based storage is being widely used as a viable solution to the problem of data storage in contexts where financial and practical considerations prohibit the use of locally based hardware and software resources. User reservations and legal constraints however have given rise to questions about the verifiability of the integrity of the stored data, especially in the case of public cloud infrastructure. A new problem has hence arisen, that of auditing stored files in order to obtain Proof of Retrievability. Secure cloud storage systems are limited by the overheads they require in order to provide the required security levels. Combined use of cloud and local computational resources is necessary in order to enable the desirable user experiences. With increasing local processing capacities, the most significant relevance is encountered in the Big data Processing paradigm. The volumes of data that need to be processed are overwhelming to such an extent that approaches which use unlimited amounts of power, for processing and storage are not feasible. This paper focuses on a recent study of hash function requirements for big data applications and an associated key - based hash function design technique that makes the real - time collection, summarization, analysis and decision making based on streaming data. A file auditing technique is proposed that uses fundamental big data mass processing operations in order to develop an efficient and reliable proof of recoverability algorithm. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Secure cloud storage Big data Proof of Retrievability data auditing data summarization Hash functions data mining

来源：评论

学校读者我要写书评

暂无评论

A unifying framework for l₀-sampling algorithms

引用

DISTRIBUTED AND PARALLEL dataBASES 2014年第3期32卷 315-335页

作者： Cormode, Graham Firmani, Donatella Univ Warwick Coventry CV4 7AL W Midlands England Univ Roma La Sapienza I-00185 Rome Italy

The problem of building an a"" (0)-sampler is to sample near-uniformly from the support set of a dynamic multiset. This problem has a variety of applications within data analysis, computational geometry and graph algorithms. In this paper, we abstract a set of steps for building an a"" (0)-sampler, based on sampling, recovery and selection. We analyze the implementation of an a"" (0)-sampler within this framework, and show how prior constructions of a"" (0)-samplers can all be expressed in terms of these steps. Our experimental contribution is to provide a first detailed study of the accuracy and computational cost of a"" (0)-samplers.

关键词： data summarization Sampling Distinct elements Graph sketches

来源：评论

学校读者我要写书评

暂无评论

Interactive data Exploration with Smart Drill-Down

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND data ENGINEERING 2019年第1期31卷 46-60页

作者： Joglekar, Manas Garcia-Molina, Hector Parameswaran, Aditya Stanford Univ Comp Sci Dept Stanford CA 94305 USA Stanford Univ Dept Elect Engn Stanford CA 94305 USA Univ Illinois UIUC Comp Sci Urbana IL 61801 USA

We present smart drill-down, an operator for interactively exploring a relational table to discover and summarize "interesting" groups of tuples. Each group of tuples is described by a rule. For instance, the rule (a,b,*, 1000) tells us that there are 1,000 tuples with value a in the first column and b in the second column (and any value in the third column). Smart drill-down presents an analyst with a list of rules that together describe interesting aspects of the table. The analyst can tailor the definition of interesting, and can interactively apply smart drill-down on an existing rule to explore that part of the table. We demonstrate that the underlying optimization problems are NP-HARD, and describe an algorithm for finding the approximately optimal list of rules to display when the user uses a smart drill-down, and a dynamic sampling scheme for efficiently interacting with large tables. Finally, we perform experiments on real datasets on our experimental prototype to demonstrate the usefulness of smart drill-down and study the performance of our algorithms.

关键词： data exploration data summarization

来源：评论

学校读者我要写书评

暂无评论

A new approximate query engine based on intelligent capture and fast transformations of granulated data summaries

引用

JOURNAL OF INTELLIGENT INFORMATION SYSTEMS 2018年第2期50卷 385-414页

作者： Slezak, Dominik Glick, Rick Betlinski, Pawel Synak, Piotr Univ Warsaw Inst Informat Warsaw Poland

We outline the processes of intelligent creation and utilization of granulated data summaries in the engine aimed at fast approximate execution of analytical SQL statements. We discuss how to use the introduced engine for the purposes of ad-hoc data exploration over large and quickly increasing data collected in a heterogeneous or distributed fashion. We focus on mechanisms that transform input data summaries into result sets representing query outcomes. We also illustrate how our computational principles can be put together with other paradigms of scaling and harnessing data analytics.

关键词： Big data processing Approximate query processing data summarization Granular computing Machine intelligence

来源：评论

学校读者我要写书评

暂无评论

Efficient and Optimal Algorithms for Tree summarization With Weighted Terminologies

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND data ENGINEERING 2023年第3期35卷 2500-2514页

作者： Zhu, Xuliang Huang, Xin Choi, Byron Xu, Jianliang Cheung, William K. Zhang, Yanchun Liu, Jiming Hong Kong Baptist Univ Dept Comp Sci Hong Kong Peoples R China Guangzhou Univ Guangzhou 510006 Peoples R China Victoria Univ Footscray Vic 3011 Australia

data summarization that presents a small subset of a dataset to users has been widely applied in numerous applications and systems. Many datasets are coded with hierarchical terminologies, e.g., gene ontology, disease ontology, to name a few. In this paper, we study the weighted tree summarization. We motivate and formulate our kWTS-problem as selecting a diverse set of k nodes to summarize a hierarchical tree T with weighted terminologies. We first propose an efficient greedy tree summarization algorithm GTS. It solves the problem with (1 -1/e)-approximation guarantee. Although GTS achieves quality-guaranteed answers approximately, but it is still not optimal. To tackle the problem optimally, we further develop a dynamic programming algorithm OTS to obtain optimal answers for kWTS-problem in O(nhk(3)) time, where n, h are the node size and height in tree T. The algorithm complexity and correctness of OTS are theoretically analyzed. In addition, we propose a useful optimization technique of tree reduction to remove useless nodes with zero weights and shrink the tree into a smaller one, which ensures the efficiency acceleration of both GTS and OTS in real-world datasets. Moreover, we illustrate one useful application of graph visualization based on the answer of k-sized tree summarization and show it in a novel case study. Extensive experimental results on real-world datasets show the effectiveness and efficiency of our proposed approximate and optimal algorithms for tree summarization. Furthermore, we conduct a usability evaluation of attractive topic recommendation on ACM Computing Classification System dataset to validate the usefulness of our model and algorithms.

关键词： Diseases Heuristic algorithms Terminology Approximation algorithms Ontologies Dynamic programming Optimization Hierarchy tree data summarization optimal algorithm top-k

来源：评论

学校读者我要写书评

暂无评论

Answering XML queries by means of data summaries

引用

ACM TRANSACTIONS ON INFORMATION SYSTEMS 2007年第3期25卷 1.1-1.33页

作者： Baralis, Elena Garza, Paolo Quintarelli, Elisa Tanca, Letizia Politecn Torino Turin Italy Politecn Milan Milan Italy

XML is a rather verbose representation of semistructured data, which may require huge amounts of storage space. We propose a summarized representation of XML data, based on the concept of instance pattern, which can both provide succinct information and be directly queried. The physical representation of instance patterns exploits itemsets or association rules to summarize the content of XML datasets. Instance patterns may be used for (possibly partially) answering queries, either when fast and approximate answers are required, or when the actual dataset is not available, for example, it is currently unreachable. Experiments on large XML documents show that instance patterns allow a significant reduction in storage space, while preserving almost entirely the completeness of the query result. Furthermore, they provide fast query answers and show good scalability on the size of the dataset, thus overcoming the document size limitation of most current XQuery engines.

关键词： theory languages association rules data mining data summarization intensional answers itemsets semistructured data

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：