Distributed Subgraph Enumeration via Backtracking-based Framework
1
Citation
38
Reference
10
Related Paper
Citation Trend
Abstract:
Finding or monitoring subgraph instances that are isomorphic to a given pattern graph in a data graph is a fundamental query operation in many graph analytic applications, such as network motif mining and fraud detection. The state-of-the-art distributed methods are inefficient in communication. They have to shuffle partial matching results during the distributed multiway join. The partial matching results may be much larger than the data graph itself. To overcome the drawback, we develop the Batch-BENU framework (B-BENU) for distributed subgraph enumeration. B-BENU executes a group of local search tasks in parallel. Each task enumerates subgraphs around a vertex in the data graph, guided by a backtracking-based execution plan. B-BENU does not shuffle any partial matching result. Instead, it stores the data graph in a distributed database. Each task queries adjacency sets of the data graph on demand. To support dynamic data graphs, we propose the concept of incremental pattern graphs and turn continuous subgraph enumeration into enumerating incremental pattern graphs at each time step. We develop the Streaming-BENU framework (S-BENU) to enumerate their matches efficiently. We implement B-BENU and S-BENU with the local database cache and the task splitting techniques. The extensive experiments show that B-BENU and S-BENU can scale to big data graphs and complex pattern graphs. They outperform the state-of-the-art methods by up to one and two orders of magnitude, respectively.Keywords:
Enumeration
Backtracking
Zeilberger's enumeration schemes can be used to completely automate the enumeration of many permutation classes. We extend his enumeration schemes so that they apply to many more permutation classes and describe the Maple package WilfPlus , which implements this process. We also compare enumeration schemes to three other systematic enumeration techniques: generating trees, substitution decompositions, and the insertion encoding.
Enumeration
Cite
Citations (49)
Abstract Using properties of ${\cal K}$ -pairs of sets, we show that every nonzero enumeration degree a bounds a nontrivial initial segment of enumeration degrees whose nonzero elements have all the same jump as a . Some consequences of this fact are derived, that hold in the local structure of the enumeration degrees, including: There is an initial segment of enumeration degrees, whose nonzero elements are all high; there is a nonsplitting high enumeration degree; every noncappable enumeration degree is high; every nonzero low enumeration degree can be capped by degrees of any possible local jump (i.e., any jump that can be realized by enumeration degrees of the local structure); every enumeration degree that bounds a nonzero element of strictly smaller jump, is bounding; every low enumeration degree below a non low enumeration degree a can be capped below a .
Enumeration
Degree (music)
Bounding overwatch
Cite
Citations (5)
Enumeration
Cite
Citations (1)
Abstract We show that every nonzero enumeration degree bounds a nonsplitting nonzero enumeration degree.
Enumeration
Bounding overwatch
Degree (music)
Cite
Citations (5)
Білім берy қоғaмның экономикaлық дaмyының негізі, әлеyметтік тұрaқтылықтың фaкторлaрының бірі, хaлықтың рyхaни-aдaмгершілік әлеyетінің және интеллектyaлдық өсyінің қaйнaр көзі ретінде бaрлық yaқыттaрдa тaптырмaс құндылық болып есептеліп келеді. Aл қaзіргідей aдaм кaпитaлын қaлыптaстырy мен дaмытy мәселесін шешy негізгі міндет ретінде қaрaстырылaтын зaмaндa хaлықтың білімдік қaжеттіліктері өсіп, жоғaры, ортa aрнayлы, кәсіби қосымшa білім aлyғa үміткерлер сaны aртa түсyде. Бұғaн жayaп ретінде білім берy ұйымдaрының сaлaлaнyы aртып, әртүрлі типтегі оқy орындaрының сaны aртyдa, білім берyдің инфрaқұрылымы, бaсқaрy формaлaры, әдістемелік, ғылыми қызмет түрлері дaмyдa. Олaрды білім aлyшылaрдың жеке сұрaныстaры мен мүмкіндіктеріне бaғыттay күшейтілyде. Осығaн орaй білімнің сaпaсынa қойылaтын тaлaптaр aртып, бұл сaлaның әлеyметпен өзaрa әрекеттестігіне негізделген құрылымдық – қызметтік дaмyының көкейтестілігі aртyдa. Мaқaлaдa «серіктестік», «әлеyметтік серіктестік», «білімдегі әлеyметтік серіктестік» ұғым- дaрының мәні aшылып, олaрдың қaлыптaсy және дaмy үрдісіне шолy жaсaлaды, жоғaры оқy орындaрындa педaгогтaрды дaярлayдa әлеyметтік серіктестердің әлеyетін пaйдaлaнyдa бaсшылыққa aлынaтын ұстaнымдaр мен тиімді жолдaры сипaттaлaды. Түйін сөздер: серіктестік, әлеyметтік серіктестік, білімдегі әлеyметтік серіктестік, бірлескен әрекет ұстaнымдaры, әлеуметтік серіктестік әлеуеті. Обрaзовaние является основой экономического рaзвития обществa, одним из фaкторов социaль- ной стaбильности, источником дyховно-нрaвственного потенциaлa и интеллектyaльного ростa людей и во все временa считaлось незaменимой ценностью. И в нaстоящее время, когдa решение проблемы формировaния и рaзвития человеческого кaпитaлa рaссмaтривaется кaк основнaя зaдaчa, рaстyт обрaзовaтельные потребности людей, yвеличивaется количество желaющих полyчить высшее, среднее, специaльное, профессионaльное дополнительное обрaзовaние. В ответ нa это yсиливaется рaзветвленность обрaзовaтельных оргaнизaций, yвеличивaется количество обрaзовaтельных оргaни- зaций рaзличного типa, рaзвивaются инфрaстрyктyрa обрaзовaния, формы yпрaвления, методическaя и нayчнaя деятельность. Yсиливaется их ориентaция нa индивидyaльные потребности и возможности обyчaющихся. В связи с этим повышaются требовaния к кaчествy обрaзовaния, возрaстaет знaчение стрyктyрно-фyнкционaльного рaзвития этой сферы нa основе взaимодействия с обществом. В стaтье рaскрывaется знaчение понятий «пaртнерство», «социaльное пaртнерство», «социaльное пaртнерство в обрaзовaнии», рaссмaтривaется процесс их стaновления и рaзвития, описывaются рyко- водящие принципы и эффективные способы использовaния потенциaлa социaльных пaртнеров в подготовке педaгогических кaдров в высших yчебных зaведениях. Ключевые словa: партнерство, социaльное пaртнерство, социaльное пaртнерство в обрaзовaнии, принципы совместного действия, поненциал социального партнерство. Education is the basis of the economic development of society, one of the factors of social stability, a source of spiritual and moral potential and intellectual growth of people and has always been considered an irreplaceable value. And at the present time, when the solution of the problem of the formation and development of human capital is considered as the main task, the educational needs of people are growing, the number of people wishing to receive higher, secondary, special, professional additional education is increasing. In response to this, the branching of educational organizations is increasing, the number of educational organizations of various types is increasing, the infrastructure of education, forms of management, methodological and scientific activities are developing. Their focus on the individual needs and capabilities of students is increasing. In this regard, the requirements for the quality of education are increasing, the importance of the structural and functional development of this sphere on the basis of interaction with society is increasing. The article reveals the meaning of the concepts of "partnership", "social partnership", "social partnership in education", examines the process of their formation and development, describes the guidelines and effective ways to use the potential of social partners in the training of teachers in higher educational institutions. Keywords: partnership, social partnership, social partnership in education, principles of joint action, the potential of social partnership.
Cite
Citations (0)
Enumeration
Cite
Citations (0)
Graph-theoretical concepts and definitions molecular codes enumeration and isomeric acyclic structures enumeration of polyhex systems enumeration of carcinogenic bay regions enumeration of aza-polygexes enumeration of Kekule Valence structures enumeration of 2-factors of planar polyhexes graph-theoretical indices the ID number.
Enumeration
Cite
Citations (42)
In this paper, we enumerate enumeration problems and algorithms. This survey is under construction. If you know some results not in this survey or there is anything wrong, please let me know.
Enumeration
Cite
Citations (21)
Abstract We give several new characterizations of the continuous enumeration degrees. The main one proves that an enumeration degree is continuous if and only if it is not half of a nontrivial relativized $\mathcal {K}$ -pair. This leads to a structural dichotomy in the enumeration degrees.
Enumeration
Degree (music)
Cite
Citations (4)
Backtracking
Enumeration
Depth-first search
Cite
Citations (1)