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

IEEE conference on Visualization

作者： U.D. Bordoloi Han-Wei Shen Department of Computer and Information Science Ohio State Uinversity USA

In this paper, we present a space efficient algorithm for speeding up isosurface extraction. Even though there exist algorithms that can achieve optimal search performance to identify isosurface cells, they prove impractical for large datasets due to a high storage overhead. With the dual goals of achieving fast isosurface extraction and simultaneously reducing the space requirement, we introduce an algorithm based on transform coding to compress the interval information of the cells in a dataset. Compression is achieved by first transforming the cell intervals (minima, maxima) into a form which allows more efficient compaction. It is followed by a dataset optimized non-uniform quantization stage. The compressed data is stored in a data structure that allows fast searches in the compression domain, thus eliminating the need to retrieve the original representation of the intervals at run-time. The space requirement of our search data structure is the mandatory cost of storing every cell ID once, plus an overhead for quantization information. The overhead is typically in the order of a few hundredths of the dataset size.

关键词： Isosurfaces data mining data structures Visualization Transform coding Quantization Runtime Information science Compaction Information retrieval

来源：评论

学校读者我要写书评

暂无评论

efficient Mining of Textual Associations

Efficient Mining of Textual Associations

引用

2003 International conference on Natural Language Processing and Knowledge Engineering

作者： Alexandre Gil Gaёl Dias Beira Interior University Computer Science Department6200-053 CovilhaPortugal

This paper describes an efficient implementation for mining textual associations from text *** order to tackle real world applications,efficient algorithms and data structures are needed to manage, in reasonable time and space,the overgrowing volume of text *** that purpose,we introduce a global architecture based on masks,suffix arrays and multidimensional arrays to implement the SENTA extractor[Dias,2002].In particular,SENTA has shown great flexibility and accuracy to mine textual associations such as collocations,cognates, morphemes and *** solution shows O(h(F)N log N)time complexity and O(N)space complexity where N is the size of the corpus and h(F)is a function of the context window size.

关键词： Suffix Arrays Masks Text Mining

来源：评论

学校读者我要写书评

暂无评论

SyncSim: a synchronous simple optimistic simulation technique based on a global parallel heap event queue

SyncSim: a synchronous simple optimistic simulation techniqu...

引用

Simulation Winter conference

作者： Prasad Zhiyong Cao Computer Science Department Georgia State University Atlanta GA USA

We developed and implemented two highly optimized optimistic discrete event simulation techniques based on an efficient and scalable parallel heap data structure as a global event queue. The primary results are (i) the design of an optimistic simulation algorithm, namely SyncSim, which does not rely on traditional state and message saving data structures, but employs only one backup state per state variable, (ii) a demonstration, through implementation of SyncSim, of an optimistic technique which overcomes the two main mutually conflicting and unbounded overheads of the existing optimistic simulation algorithms: SyncSim bounds the additional space requirements to just one copy per state variable and drastically limits the number of rollbacks encountered. Furthermore, SyncSim beats the highly optimized traditional simulator simglobal on a wide variety of large networks on an Origin-2000 computer. The algorithm SyncSim could form a basis for a good parallelizing engine attachable relatively easily to an existing serial simulator.

关键词： Discrete event simulation Computational modeling Design optimization Computer simulation data structures Algorithm design and analysis Clocks Computer science Computer networks Engines

来源：评论

学校读者我要写书评

暂无评论

Adaptive data structures for IP lookups

Adaptive data structures for IP lookups

引用

IEEE Annual Joint conference: INFOCOM, IEEE Computer and Communications Societies

作者： I. Ioannidis Ananth Grama M. Atallah Department of Computer Sciences Purdue University West Lafayette IN USA

The problem of efficient data structures for IP lookups has been well studied in literature. Techniques such as LC tries and extensible hashing are commonly used. In this paper, we address the problem of generalizing LC tries and extensible hashing, based on traces of past lookups, to provide performance guarantees for memory sub-optimal structures. As a specific example, if a memory-optimal (LC) trie takes 6 MB and the total memory at the router is 8 MB, how should the trie be modified to make best use of the 2 MB of excess memory? We present a greedy algorithm for this problem and prove that, if for the optimal data structure there are b fewer memory accesses on average for each lookup compared with the original trie, the solution produced by the greedy algorithm will have 9/spl times/b/22 fewer memory accesses on average (compared to the original trie). An efficient implementation of this algorithm presents significant additional challenges. We describe an implementation with a time complexity of O(/spl xi/(d)n /spl times/ log n) and a space complexity of O(n), where n is the number of nodes of the trie and d its depth. The depth of a trie is fixed for a given version of the Internet protocol and is typically O(log n). In this case, /spl xi/(d) = O(log/sup 2/ n). We demonstrate experimentally the performance and scalability of the algorithm on actual routing data. We also show that our algorithm significantly outperforms extensible hashing for the same amount of memory.

关键词： data structures Greedy algorithms Internet Protocols Scalability Routing Table lookup Turning Probability distribution Memory management

来源：评论

学校读者我要写书评

暂无评论

Symbolic model checking for real time systems using difference typed decision graphs

Symbolic model checking for real time systems using differen...

引用

ACS/IEEE International conference on Computer Systems and Applications

作者： S. Ayadi R. Robbana FST Tunisia

Summary form only given. In symbolic model checking of untimed systems, the general approach is based on BDDs (Binary Decision Diagrams) representation. Concurrently, TDGs (typed Decision Graphs) were proposed in another context, bring a better profit of capacity memory. However, the symbolic method do not easily generalize to models that contain variables ranging over noncountable domains like for example real-time systems where time is modeled using continuous real variables and the behavior of a system is specified using constraints on these variables. To solve the reachability problem for a timed system, there are very few results on how model checking is efficient, such as the technique of DDDs (Difference Decision Diagrams) representing difference constraints on clocks. But, it remains an open problem to find algorithms and data structures that work just as well for timed systems as BDDs do for untimed systems. We present a methodology for the symbolic model checker using a new technique of representation of timed systems: the DTDGs, Difference Typed Decision Graphs that is a combination of TDGs and DDDs. Then, our approach consists in analyzing timed systems symbolically, and describe the corresponding data structure (DTDGs) for representing the state space of a timed system. For that, we use timed graphs for the modelling of timed systems. This result allows us to analyse timed systems with both the discrete part of states and the associated timing information. Hence the motivation is about symbolic model checking for timed systems based on difference typed decision graphs.

关键词： Real time systems data structures Boolean functions Clocks State-space methods Information analysis Timing Logic

来源：评论

学校读者我要写书评

暂无评论

Eliminating redundancies in SAT search trees

Eliminating redundancies in SAT search trees

引用

International conference on Tools for Artificial Intelligence (ICTAI)

作者： R. Ostrowski B. Mazure L. Sais E. Gregoire CRIL CNRS Université d'Artois Lens France

Conflict analysis is a powerful paradigm of backtrack search algorithms, in particular for solving satisfiability problems arising from practical applications. Accordingly, most recent Boolean satisfiability solvers implement forms of conflict analysis, at least to some extent. In this paper, a branching criterion initially introduced by Purdom is revisited and extended. Contrary to the author's a priori analysis, it is shown very efficient from a practical point of view in that it allows search trees in SAT solving to be pruned in a significant way while obeying an interesting time and space trade-off. More precisely, we show that redundancies during the search process can be avoided without adding new constraints explicitly. Moreover, the technique can be used not only to prune branches in the search tree, but also to derive implied literals. Extensive experimental results illustrate the feasibility and practical interest of this approach.

关键词： Algorithm design and analysis Artificial intelligence Lenses NP-complete problem Computer science Very large scale integration Buildings Surges data structures Information analysis

来源：评论

学校读者我要写书评

暂无评论

efficient approximation of optimization queries under parametric aggregation constraints 03

引用

Proceedings of the 29th international conference on Very large data bases - Volume 29

作者： Sudipto Guha Dimitrios Gunopoulos Nick Koudas Divesh Srivastava Michail Vlachos University of Pennsylvania University of California AT&T Labs-Research

ISBN: (纸本)9780127224428

We introduce and study a new class of queries that we refer to as OPAC (optimization under parametric aggregation constraints) queries. Such queries aim to identify sets of database tuples that constitute solutions of a large class of optimization problems involving the database tuples. The constraints and the objective function are specified in terms of aggregate functions of relational attributes, and the parameter values identify the constants used in the aggregation *** develop algorithms that preprocess relations and construct indices to efficiently provide answers to OPAC queries. The answers returned by our indices are approximate, not exact, and provide guarantees for their accuracy. Moreover, the indices can be tuned easily to meet desired accuracy levels, providing a graceful tradeoff between answer accuracy and index space. We present the results of a thorough experimental evaluation analyzing the impact of several parameters on the accuracy and performance of our techniques. Our results indicate that our methodology is effective and can be deployed easily, utilizing index structures such as R-trees.

关键词：

来源：评论

学校读者我要写书评

暂无评论

algorithms and programming models for efficient representation of XML for Internet applications

引用

COMPUTER NETWORKS-THE INTERNATIONAL JOURNAL OF COMPUTER AND TELECOMMUNICATIONS NETWORKING 2002年第5期39卷 681-697页

作者： Sundaresan, N Moussa, R NehaNet Corp San Jose CA 95131 USA

XML is poised to take the World-Wide-Web to the next level of innovation. XML data, large or small, with or without associated schema, will be exchanged between increasing numbers of applications running on diverse devices. efficient storage and transportation of such data is an important issue. We have designed a system called Millau and a series of algorithms for efficient encoding and representation of XML structures. In this paper we describe some of the newer algorithms and APIs in our system for compression of XML structures and data. Our compression algorithms, in addition to separating structure and text for compression, take advantage of the associated schema (if available) in compressing the structure. We also quantify XML documents and their schema with the purpose of defining a decision logic to apply the appropriate compression algorithm for a document or a set of documents following a particular schema. Our system also defines a programming model corresponding to XML Document Object Model and Simple API for XML streams and documents in compressed form. Our experiments have shown significant performance gains of our algorithms and APIs. We describe some of these results in this paper. We also describe some Web applications based on our system. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： XML DOM SAX compression WBXML

来源：评论

学校读者我要写书评

暂无评论

algorithms and programming models for efficient representation of XML for Internet applications 01

Algorithms and programming models for efficient representati...

引用

10th International World Wide Web conference

作者： Sundaresan, N Moussa, R NehaNet Corp San Jose CA 95131 USA

ISBN: (纸本)9781581133486

关键词： XML DOM SAX compression WBXML

来源：评论

学校读者我要写书评

暂无评论

Approximating a data stream for querying and estimation: algorithms and performance evaluation

Approximating a data stream for querying and estimation: Alg...

引用

18th International conference on data Engineering

作者： Guha, S Koudas, N Univ Penn Philadelphia PA 19104 USA

ISBN: (纸本)0769515312

Obtaining fast and good quality approximations to data distributions is a problem of central interest to database management. A variety of popular database applications including, approximate querying, similarity searching and data mining in most application domains, rely on such good quality approximations. Histogram based approximation is a very popular method in database theory and practice to succinctly represent a data distribution in a space efficient manner. In this paper, we place the problem of histogram construction into perspective and we generalize it by raising the requirement of a finite data set and/or known data set size. We consider the case of an infinite data set on which data arrive continuously forming an infinite data stream. In this context, we present the first single pass algorithms capable of constructing histograms of provable good quality;We present algorithms for the fixed window variant of the basic histogram construction problem, supporting incremental maintenance of the, histograms. The proposed algorithms trade accuracy for speed and allow for a graceful tradeoff between the two, based on application requirements. In the case of approximate queries on infinite data streams, we present a detailed experimental evaluation comparing our algorithms with other applicable techniques using real data sets, demonstrating the superiority of our proposal.

关键词： Query languages

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：