research-article

Searching connected API subgraph via text phrases

Authors:

Wing-Kwan Chan,

David LoAuthors Info & Claims

FSE '12: Proceedings of the ACM SIGSOFT 20th International Symposium on the Foundations of Software Engineering

Article No.: 10, Pages 1 - 11

https://doi.org/10.1145/2393596.2393606

Published: 11 November 2012 Publication History

Abstract

Reusing APIs of existing libraries is a common practice during software development, but searching suitable APIs and their usages can be time-consuming [6]. In this paper, we study a new and more practical approach to help users find usages of APIs given only simple text phrases, when users have limited knowledge about an API library. We model API invocations as an API graph and aim to find an optimum connected subgraph that meets users' search needs.

The problem is challenging since the search space in an API graph is very huge. We start with a greedy subgraph search algorithm which returns a connected subgraph containing nodes with high textual similarity to the query phrases. Two refinement techniques are proposed to improve the quality of the returned subgraph. Furthermore, as the greedy subgraph search algorithm relies on online query of shortest path between two graph nodes, we propose a space-efficient compressed shortest path indexing scheme that can efficiently recover the exact shortest path. We conduct extensive experiments to show that the proposed subgraph search approach for API recommendation is very effective in that it boosts the average F₁-measure of the state-of-the-art approach, Portfolio [15], on two groups of real-life queries by 64% and 36% respectively.

References

[1]

S. K. Bajracharya, T. C. Ngo, E. Linstead, Y. Dou, P. Rigor, P. Baldi, and C. V. Lopes. Sourcerer: a search engine for open source code supporting structure-based search. In OOPSLA Companion, pages 681--682, 2006.

Digital Library

[2]

S. Brin and L. Page. The anatomy of a large-scale hypertextual web search engine. Computer Networks, 30(1--7):107--117, 1998.

Digital Library

[3]

S.-J. Chen and L. Lin. Modeling team member characteristics for the formation of a multifunctional team in concurrent engineering. IEEE Transactions on Engineering Management, 51(2):111--124, 2004.

[4]

F. Crestani. Application of spreading activation techniques in information retrieval. Artif. Intell. Rev., 11(6):453--482, 1997.

Digital Library

[5]

K. Grant and D. Mould. Combining heuristic and landmark search for path planning. In Future Play, pages 9--16, 2008.

Digital Library

[6]

R. Hoffmann, J. Fogarty, and D. S. Weld. Assieme: finding and leveraging implicit references in a web search interface for programmers. In UIST, pages 13--22, 2007.

Digital Library

[7]

F. K. Hwang, D. S. Richards, and P. Winter. The Steiner Tree Problem. North-Holland, Amsterdam, Netherlands, 1992.

[8]

K. Kamel, N. Tubaiz, O. AlKoky, and Z. AlAghbari. Toward forming an effective team using social network. In IIT, pages 308--312, 2011.

[9]

M. Kargar and A. An. Keyword search in graphs: Finding r-cliques. PVLDB, 4(10):681--692, 2011.

Digital Library

[10]

A. J. Ko, B. A. Myers, and H. H. Aung. Six learning barriers in end-user programming systems. In VL/HCC, pages 199--206, 2004.

Digital Library

[11]

T. Lappas, K. Liu, and E. Terzi. Finding a team of experts in social networks. In KDD, pages 467--476, 2009.

Digital Library

[12]

C.-T. Li and M.-K. Shan. Team formation for generalized tasks in expertise social networks. In SocialCom/PASSAT, pages 9--16, 2010.

Digital Library

[13]

F. Long, X. Wang, and Y. Cai. Api hyperlinking via structural overlap. In ESEC/SIGSOFT FSE, pages 203--212, 2009.

Digital Library

[14]

D. Mandelin, L. Xu, R. Bodík, and D. Kimelman. Jungloid mining: helping to navigate the api jungle. In PLDI, pages 48--61, 2005.

Digital Library

[15]

C. McMillan, M. Grechanik, D. Poshyvanyk, Q. Xie, and C. Fu. Portfolio: finding relevant functions and their usage. In ICSE, pages 111--120, 2011.

Digital Library

[16]

C. McMillan, D. Poshyvanyk, and M. Grechanik. Recommending source code examples via api call usages and documentation. In Proceedings of the 2nd International Workshop on Recommendation Systems for Software Engineering, pages 21--25, 2010.

Digital Library

[17]

M. F. Porter. Readings in information retrieval. chapter An algorithm for suffix stripping, pages 313--316. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1997.

Digital Library

[18]

D. Puppin and F. Silvestri. The social network of java classes. In SAC, pages 1409--1413, 2006.

Digital Library

[19]

M. Qiao, H. Cheng, and J. X. Yu. Querying shortest path distance with bounded errors in large graphs. In SSDBM, pages 255--273, 2011.

Digital Library

[20]

C. Scaffidi. Why are apis difficult to learn and use? ACM Crossroads, 12(4):4, 2006.

Digital Library

[21]

H. Wi, S. Oh, J. Mun, and M. Jung. A team formation model based on knowledge and collaboration. Expert Syst. Appl., 36(5):9121--9134, 2009.

Digital Library

[22]

J. X. Yu, L. Qin, and L. Chang. Keyword search in relational databases: A survey. IEEE Data Eng. Bull., 33(1):67--78, 2010.

[23]

Q. Zhang, W. Zheng, and M. R. Lyu. Flow-augmented call graph: A new foundation for taming api complexity. In FASE, pages 386--400, 2011.

Digital Library

[24]

W. Zheng, Q. Zhang, and M. R. Lyu. Cross-library api recommendation using web search engines. In SIGSOFT FSE, pages 480--483, 2011.

Digital Library

[25]

H. Zhong, T. Xie, L. Zhang, J. Pei, and H. Mei. Mapo: Mining and recommending api usage patterns. In ECOOP, pages 318--343, 2009.

Digital Library

[26]

A. Zzkarian and A. Kusiak. Forming teams: an analytical approach. IIE Transactions, 31:85--97, 1999.

Cited By

Wen WZhang BHu YZhu XWang Z(2024)An API Recommendation Method for Querying Mobile Computing ProblemsInternational Journal of Cognitive Informatics and Natural Intelligence10.4018/IJCINI.34442218:1(1-16)Online publication date: 30-May-2024
https://doi.org/10.4018/IJCINI.344422
Ma ZAn SXie BLin ZBaysal OLinares-Vasquez MMoran KSteinmacher I(2024)Compositional API Recommendation for Library-Oriented Code GenerationProceedings of the 32nd IEEE/ACM International Conference on Program Comprehension10.1145/3643916.3644403(87-98)Online publication date: 15-Apr-2024
https://dl.acm.org/doi/10.1145/3643916.3644403
Kong XLv ZChen CChang HLi NZhang F(2024)Code Recommendation for Schema Evolution of Mimic Storage SystemsInternational Journal of Software Engineering and Knowledge Engineering10.1142/S0218194024500499(1-22)Online publication date: 28-Oct-2024
https://doi.org/10.1142/S0218194024500499
Show More Cited By

Index Terms

Searching connected API subgraph via text phrases
1. Social and professional topics
  1. Professional topics
    1. Management of computing and information systems
      1. Project and people management
2. Software and its engineering
  1. Software notations and tools
    1. Software libraries and repositories

Recommendations

API method recommendation without worrying about the task-API knowledge gap
ASE '18: Proceedings of the 33rd ACM/IEEE International Conference on Automated Software Engineering

Developers often need to search for appropriate APIs for their programming tasks. Although most libraries have API reference documentation, it is not easy to find appropriate APIs due to the lexical gap and knowledge gap between the natural language ...
Graph Embedding Based API Graph Search and Recommendation
Abstract
Searching application programming interfaces (APIs) is very important for developers to reuse software projects. Existing natural language based API search mainly faces the following challenges. 1) More accurate results are required as software ...
The balanced connected subgraph problem
Abstract
The problem of computing induced subgraphs that satisfy some specified restrictions arises in various applications of graph algorithms and has been well studied. In this paper, we consider the following ▪ ( ▪ ) problem. The input is a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

FSE '12: Proceedings of the ACM SIGSOFT 20th International Symposium on the Foundations of Software Engineering

November 2012

494 pages

ISBN:9781450316149

DOI:10.1145/2393596

General Chair:
Will Tracz
Lockheed Martin Fellow Emeritus
,
Program Chairs:
Martin Robillard
McGill University
,
Tevfik Bultan
University of California, Santa Barbara

Copyright © 2012 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGSOFT: ACM Special Interest Group on Software Engineering

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 November 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Research Grants Council, University Grants Committee, Hong Kong

Conference

SIGSOFT/FSE'12

Sponsor:

SIGSOFT

SIGSOFT/FSE'12: 20th ACM SIGSOFT Symposium on the Foundations of Software Engineering

November 11 - 16, 2012

North Carolina, Cary

Acceptance Rates

Overall Acceptance Rate 17 of 128 submissions, 13%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

109
Total Citations
View Citations
505
Total Downloads

Downloads (Last 12 months)26
Downloads (Last 6 weeks)3

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wen WZhang BHu YZhu XWang Z(2024)An API Recommendation Method for Querying Mobile Computing ProblemsInternational Journal of Cognitive Informatics and Natural Intelligence10.4018/IJCINI.34442218:1(1-16)Online publication date: 30-May-2024
https://doi.org/10.4018/IJCINI.344422
Ma ZAn SXie BLin ZBaysal OLinares-Vasquez MMoran KSteinmacher I(2024)Compositional API Recommendation for Library-Oriented Code GenerationProceedings of the 32nd IEEE/ACM International Conference on Program Comprehension10.1145/3643916.3644403(87-98)Online publication date: 15-Apr-2024
https://dl.acm.org/doi/10.1145/3643916.3644403
Kong XLv ZChen CChang HLi NZhang F(2024)Code Recommendation for Schema Evolution of Mimic Storage SystemsInternational Journal of Software Engineering and Knowledge Engineering10.1142/S0218194024500499(1-22)Online publication date: 28-Oct-2024
https://doi.org/10.1142/S0218194024500499
Wang YFang YGao CChen L(2024)API Recommendation for Novice Programmers: Build a Bridge of Query-Task Knowledge GapIEEE Transactions on Reliability10.1109/TR.2024.336192273:3(1473-1486)Online publication date: Sep-2024
https://doi.org/10.1109/TR.2024.3361922
Chen YGao CZhu MLiao QWang YXu G(2024)APIGen: Generative API Method Recommendation2024 IEEE International Conference on Software Analysis, Evolution and Reengineering (SANER)10.1109/SANER60148.2024.00025(171-182)Online publication date: 12-Mar-2024
https://doi.org/10.1109/SANER60148.2024.00025
Zhang XShen GHuang ZYu YWang K(2024)FuEPRe: a fusing embedding method with attention for post recommendationService Oriented Computing and Applications10.1007/s11761-024-00386-y18:1(67-79)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1007/s11761-024-00386-y
Shin JWei MWang JShi LWang S(2023)The Good, the Bad, and the Missing: Neural Code Generation for Machine Learning TasksACM Transactions on Software Engineering and Methodology10.1145/363000933:2(1-24)Online publication date: 22-Dec-2023
https://dl.acm.org/doi/10.1145/3630009
Rahman MRoy C(2023)A Systematic Review of Automated Query Reformulations in Source Code SearchACM Transactions on Software Engineering and Methodology10.1145/360717932:6(1-79)Online publication date: 4-Jul-2023
https://dl.acm.org/doi/10.1145/3607179
Kim KGhatpande SKim DZhou XLiu KBissyandé TKlein JLe Traon Y(2023)Big Code Search: A BibliographyACM Computing Surveys10.1145/360490556:1(1-49)Online publication date: 26-Aug-2023
https://dl.acm.org/doi/10.1145/3604905
Zeng CYu YLi SXia XWang ZGeng MBai LDong WLiao X(2023)deGraphCS: Embedding Variable-based Flow Graph for Neural Code SearchACM Transactions on Software Engineering and Methodology10.1145/354606632:2(1-27)Online publication date: 30-Mar-2023
https://dl.acm.org/doi/10.1145/3546066
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents