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

IEEE 36th International Conference on Data Engineering (ICDE)

作者： Ni, Wangze Cheng, Peng Chen, Lei Lin, Xuemin Hong Kong Univ Sci & Technol Hong Kong Peoples R China East China Normal Univ Shanghai Peoples R China Univ New South Wales Sydney NSW Australia

ISBN: (纸本)9781728129037

Ubiquitous smart devices and high-quality wireless networks enable people to participate in spatial crowdsourcing tasks easily, which require workers to physically move to specific locations to conduct their assigned tasks. Spatial crowdsourcing has attracted much attention from both academia and industry. In this paper, we consider a spatial crowdsourcing scenario, where the tasks may have some dependencies among them. Specifically, one task can only be dispatched when its dependent tasks have already been assigned. In fact, task dependencies are quite common in many real-life applications, such as house repairing and holding sports games. We formally define the dependency-aware spatial crowdsourcing (DA-SC), which focuses on finding an optimal worker-and-task assignment under the constraints of dependencies, skills of workers, moving distances and deadlines to maximize the successfully assigned tasks. We prove that the DA-SC problem is NP-hard and thus intractable. Therefore, we propose two approximation algorithms, including a greedy approach and a game-theoretic approach, which can guarantee the approximate bounds of the results in each batch process. Through extensive experiments on both real and synthetic data sets, we demonstrate the efficiency and effectiveness of our DA-SC approaches.

关键词： Spatial Crowdsourcing Task Assignment approximate algorithm

来源：评论

学校读者我要写书评

暂无评论

Complexity measures for matrix multiplication algorithms

引用

Calcolo 1980年第1期17卷 77-86页

作者： Romani, F. Istituto di Elaborazione della Informazione CNR Pisa Italy

A new class of algorithms for the computation of bilinear forms has been recently introduced [1, 3]. These algorithms approximate the result with an arbitrarily small error. Such approximate algorithms may have a multiplicative complexity smaller than exact ones. On the other hand any comparison between approximate and exact algorithms has to take into account the complexity-stability relations. In this paper some complexity measures for matrix multiplication algorithms are discussed and applied to the evaluation of exact and approximate algorithms. Multiplicative complexity is shown to remain a valid comparison test and the cost of approximation appears to be only a logarithmic factor. © 1980 Instituto di Elaborazione della Informazione del CNR.

关键词： Bilinear Form Matrix Multiplication Complexity Measure approximate algorithm Recursive Partitioning

来源：评论

学校读者我要写书评

暂无评论

A Heuristic Method for Balanced Graph Partitioning: An Application for the Demarcation of Preventive Police Patrol Areas

引用

11th Ibero-American Conference on Artificial Intelligence

作者： Assuncao, Thiago Furtado, Vasco Univ Fortaleza Grad Program Appl Informat MIA BR-60811905 Fortaleza Ceara Brazil

ISBN: (纸本)9783540883081

In this paper we describe a heuristic method, based on graph-partitioning algorithms, with the purpose of improving the demarcation of areas for police patrolling. This demarcation seeks to homogenize the number of crimes among the patrol regions. If the map of a particular region is taken as a graph, we can say that the problem faced by police forces (typically preventive police) is similar to the problem of finding balanced connected q partitions of graphs (BCPq). Since this is a problem belonging to the NP-Hard class, approximate algorithms are the most suitable for solving such a problem. The method described in this article obtains results nearest those considered optimal for the more general case of BCPq, for q >= 2.

关键词： approximate algorithm graphs heuristic method balanced connected partition

来源：评论

学校读者我要写书评

暂无评论

MCILS: Monte-Carlo Interpolation Least-Square algorithm for Approximation of Edge-Reliability Polynomial 9

MCILS: Monte-Carlo Interpolation Least-Square Algorithm for ...

引用

9th International Conference on Computer and Knowledge Engineering (ICCKE)

作者： Hadian-Rasanan, A. H. Rahmati, D. Gorgin, S. Rad, J. A. Inst Res Fundamental Sci Sch Comp Sci Farmanieh Campus Tehran Iran Shahid Beheshti Univ Fac Comp Sci & Engn Tehran Iran Iranian Res Org Sci & Technol IROST Dept Elect Engn & Informat Technol Tehran Iran Shahid Beheshti Univ Inst Cognit & Brain Sci Dept Cognit Modeling Tehran Iran

ISBN: (纸本)9781728150758

Edge reliability problem has many applications in different field of science and engineering such as: cognitive science, neuroscience, electrical engineering, network science and so on. The major challenge in this problem is time complexity of the exact algorithm. Computing the reliability of a network is NP-hard problem. So, computing the reliability of a large scale network is a challenging problem. In this paper, we present a novel algorithm based on a hybrid Monte-Carlo, interpolation and least-square methods to approximate the reliability of a network. The presented algorithm is applied on some networks that the exact reliability polynomial is available for them. the experiments show that the presented algorithm is accurate and robust.

关键词： Monte-Carlo method Chebyshev interpolation Edge reliability polynomial approximate algorithm

来源：评论

学校读者我要写书评

暂无评论

Packet Scheduling in a Low-Latency Optical Switch with Wavelength Division Multiplexing and Electronic Buffer

Packet Scheduling in a Low-Latency Optical Switch with Wavel...

引用

IEEE INFOCOM Conference

作者： Liu, Lin Zhang, Zhenghao Yang, Yuanyuan SUNY Stony Brook Dept Elect & Comp Engn Stony Brook NY 11794 USA Florida State Univ Dept Commun Sci Tallahassee 30306 FL USA

ISBN: (纸本)9781424499212

Optical switches are widely considered as the most promising candidate to provide ultra-high speed interconnections. Due to the difficulty in implementing all-optical buffer, optical switches with electronic buffers have been proposed recently [1] [4] [5]. Among these switches, the Optical Cut-Through (OpCut) switch has the capability to achieve low latency and minimize optical-electronic-optical (O/E/O) conversions. In this paper, we consider packet scheduling in this switch with wavelength division multiplexing (WDM). Our goal is to maximize throughput and maintain packet order at the same time. While we prove that such an optimal scheduling problem is NP-hard and inapproximable in polynomial time within any constant factor by reducing it to the set packing problem, we present an approximation algorithm that maintains packet order and approximates the optimal scheduling within a factor of root 2Nk with regard to the number of packets transmitted, where N is the switch size and k is the number of wavelengths multiplexed on each fiber. This result is in line with the best known approximation algorithm for set packing. Based on the approximation algorithm, we also give practical schedulers that can be implemented in fast optical switches. Simulation results show that the schedulers achieve close performance to the ideal WDM output-queued switch in terms of packet delay under various traffic models.

关键词： Optical switch wavelength division multiplexing (WDM) electronic buffer packet scheduling approximate algorithm

来源：评论

学校读者我要写书评

暂无评论

Bubble Sketch: A High-performance and Memory-efficient Sketch for Finding Top-k Items in Data Streams 24

Bubble Sketch: A High-performance and Memory-efficient Sketc...

引用

33rd ACM International Conference on Information and Knowledge Management (CIKM)

作者： Cao, Lu Shi, Qilong Liu, Yuxi Zheng, Hanyue Xin, Yao Li, Wenjun Yang, Tong Wang, Yangyang Xu, Yang Zhang, Weizhe Xu, Mingwei Harbin Inst Technol Shenzhen Peoples R China Tsinghua Univ Beijing Peoples R China Pengcheng Lab Shenzhen Peoples R China Peking Univ Beijing Peoples R China Guangzhou Univ Guangzhou Peoples R China Fudan Univ Shanghai Peoples R China

ISBN: (纸本)9798400704369

Sketch algorithms are crucial for identifying top-k items in largescale data streams. Existing methods often compromise between performance and accuracy, unable to efficiently handle increasing data volumes with limited memory. We present Bubble Sketch, a compact algorithm that excels in both performance and accuracy. Bubble Sketch achieves this by (1) Recording only full keys of hot items, significantly reducing memory usage, and (2) Using threshold relocation to resolve conflicts, enhancing detection accuracy. Unlike traditional methods, Bubble Sketch eliminates the need for a MinHeap, ensuring fast processing speeds. Experiments show Bubble Sketch outperforms the other seven algorithms compared, with the highest throughput and precision, and surpasses HeavyKeeper in accuracy by up to two orders of magnitude.

关键词： Data stream approximate algorithm Sketch Top-k

来源：评论

学校读者我要写书评

暂无评论

Distributed Triangle Counting algorithms in Simple Graph Stream 25

Distributed Triangle Counting Algorithms in Simple Graph Str...

引用

25th IEEE International Conference on Parallel and Distributed Systems (IEEE ICPADS)

作者： Yu, Mengdi Song, Chao Gu, Jiqing Liu, Ming Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu Peoples R China Univ Elect Sci & Technol China Big Data Res Ctr Chengdu Peoples R China

ISBN: (纸本)9781728125831

Recently, the counting algorithm of local topology structures, such as triangles, has been widely used in social network analysis, recommendation systems, user portraits and other fields. At present, one-pass streaming algorithm for counting global and local triangles has been widely studied, and most researches focus on the single-machine streaming algorithm in a 'offline+batch processing' mode. However, researches on distributed online algorithm on multiple machines are still in its infancy, and this stage has not been thoroughly studied. In this paper, we investigate the triangle counting problem in large-scale simple undirected graphs whose edges arrive as a stream. We propose two distributed online streaming algorithms to estimate the global number of triangles, which are based on the current best performance sampling-based streaming algorithm. We mainly realize the reasonable partition of the graph stream, so that each worker independently estimates the number of triangles in a subgraph of the graph stream. Experimental results show that our algorithms reduce the estimation error and are several times more accurate than state-of-the-art streaming algorithms.

关键词： approximate algorithm distributed streaming algorithm graph algorithm graph stream triangle counting algorithm

来源：评论

学校读者我要写书评

暂无评论

Distributed Fair k-Center Clustering Problems with Outliers 22nd

Distributed Fair k-Center Clustering Problems with Outliers

引用

22nd International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT 2021)

作者： Yuan, Fan Diao, Luhong Du, Donglei Liu, Lei Beijing Univ Technol Dept Operat Res & Informat Engn Beijing 100124 Peoples R China Univ New Brunswick Fac Management Fredericton NB E3B 5A3 Canada

ISBN: (纸本)9783030967727;9783030967710

Big data clustering is a fundamental problem with a vast number of applications. Due to the increasing size of data, interests in clustering problems in distributed computation models have increased. On the other hand, because important decision making is being automated with the help of algorithms, therefore, fairness in algorithms has become an especially important research topic. In this work, we design new distributed algorithms for the fair k-center problem with outliers. Our main contributions are: (1) In the fair k-center problem with outliers setting we give a 4-approximation ratio algorithm. (2) In the distributed fair k-center problem with outliers setting we give a 18-approximation ratio algorithm.

关键词： Clustering problem approximate algorithm Fair k-center problem with outliers Distributed fair k-center problem with outliers

来源：评论

学校读者我要写书评

暂无评论

Maximizing Range Sum in Trajectory Data 38

Maximizing Range Sum in Trajectory Data

引用

38th IEEE International Conference on Data Engineering (ICDE)

作者： Zhang, Kaiqi Gao, Hong Han, Xixian Chen, Jian Li, Jianzhong Harbin Inst Technol Sch Comp Sci Harbin Peoples R China Chinese Acad Sci Shenzhen Inst Adv Technol Fac Comp Sci & Control Engn Shenzhen Peoples R China

ISBN: (数字)9781665408837

ISBN: (纸本)9781665408837

Maximizing Range Sum (MaxRS) query is a basic operation in computational geometry and database communities. Given a set of weighted objects in 2-dimensional space and a rectangle, MaxRS query aims to find an optimal position of the rectangle to maximize the total weight of covered objects (i.e., Range Sum). All the existing literature for MaxRS query commonly assumes that every object is associated with a unique point. In real applications, however, every object (e.g., GPS-enabled moving vehicle) is related to a trajectory including a sequence of points, which goes beyond this restrictive assumption. How to tackle the problem of MaxRS query in trajectory data (MaxRST) is important and challenging. In this paper, we propose the definition of MaxRST query where a trajectory is covered by a rectangle if at least one of points in the trajectory is enclosed by the rectangle. We propose a novel method to solve MaxRST query by converting it to rectilinear polygon intersection problem. Then, an interval-tree-based partitioning technique is developed to efficiently settle rectilinear polygon intersection problem. To further shorten the response time, we present (epsilon, delta)-approximate MaxRST query, which returns an approximate answer having the relative error epsilon to the optimal covered weight with probability at least delta. Furthermore, two complementary sampling-based (epsilon, delta)-approximate MaxRST algorithms are proposed. One performs random sampling with replacements on rectilinear polygons and the sample size is irrelevant to the number of trajectories. The other employs grid shifting technique to reduce sample size yet requires an extra cost for grid construction. The theoretical analysis and experimental results show that our proposed algorithms have high performance in terms of efficiency and accuracy.

关键词： MaxRS query approximate algorithm Sampling Trajectory data

来源：评论

学校读者我要写书评

暂无评论

Generating a simple polygonalizations

Generating a simple polygonalizations

引用

15th International Conference on Information Visualisation (IV)

作者： Muravitskiy, V. Tereshchenko, V. Natl Taras Shevchenko Univ Kiev Kiev Ukraine

ISBN: (纸本)9780769544762

We consider the methods of construction simple polygons for a set S of n points and applying them for searching the minimal area polygon. In this paper we propose the approximate algorithm, which generates the simple polygonalizations of a fixed point set and finds the minimum area polygon, in O(n(3)) time and using O(n(2)) memory.

关键词： simple polygon approximate algorithm minimal area polygon polygonalizations

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：